题目描述

给定一个 $R \times C$ 的网格，每个格子里有若干颗花生。你需要从左上角出发，每次只能向右或向下移动，最终到达右下角。每经过一个格子，就能收集该格子的所有花生。请计算你最多能收集到多少颗花生。

输入格式

第一行：一个整数 $T$，表示测试数据的组数。

对于每组数据：

1. 第一行：两个整数 $R$ 和 $C$，分别表示网格的行数和列数。
2. 接下来 $R$ 行：每行包含 $C$ 个非负整数 $M$，表示对应格子里的花生数量。

输出格式

对于每组数据，输出一行一个整数，表示能收集到的最大花生数。

样例

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

8
16

样例解释

• 第一组：网格为

  1 1
  3 4
  

  最佳路径：1 → 3 → 4，总和为 8。
• 第二组：网格为

  2 3 4
  1 6 5
  

  最佳路径：2 → 3 → 6 → 5，总和为 16。

数据范围

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