题目描述

小可参加了学校的"智慧校园"闯关活动。校园被设计成一个 $R$ 行 $C$ 列的网格状区域，每个格点代表一个打卡点，放有若干积分。小可从西北角（左上角）的校门口出发，目标是到达东南角（右下角）的领奖处。

活动规则如下：

• 小可每次只能向东（右）或向南（下）移动一个打卡点
• 不能向西或向北回头走
• 经过一个打卡点时，可以收集该点的所有积分

请帮助小可规划路线，使得从起点到终点能够收集到最多的积分。

输入

第一行输入一个整数 $T$，表示挑战场景的数量。$(1 \le T \le 100)$

对于每个挑战场景：

• 第一行包含两个整数 $R$ 和 $C$，分别表示校园区域的行数和列数。$(1 \le R, C \le 100)$
• 接下来 $R$ 行，每行包含 $C$ 个整数，表示每个打卡点的积分数量。每个整数 $M$ 表示该点的积分数。$(0 \le M \le 1000)$

输出

对于每个挑战场景，输出一行，包含一个整数，表示小可最多能收集到的积分总数。

样例

2

2 2
1 1
3 4

2 3
2 3 4
1 6 5

8
16

样例解释

第一组：

选 $(1,\ 1)$、$(2,\ 1)$、$(2,\ 2)$，共 $1+3+4=8$。

第二组：

选 $(1,\ 1)$、$(1,\ 2)$、$(2,\ 2)$、$(2,\ 3)$，共 $2+3+6+5=16$。

数据范围

• $1 \le T \le 100$
• $1 \le R, C \le 100$
• $0 \le M \le 1000$