题目描述

王老师又开始了淘汰学生之路。
王老师有一个 R 行 C 列的网格S，每个小格子标有一个正数或负数。负数表示王老师决定淘汰 -Sij个学生，正数表示王老师决定加入 Sij 个学生。然而当班上没有学生之后，王老师就会被学校开除，他就再也没法淘汰或加入学生了。
王老师从左上角的格子(1, 1)出发，要到达右下角(R, C)。对于每个格子(i, j)，王老师可以选择向右到(i, j+1)或者向下到(i+1, j)，但是不能走出这整个格子 S 的边框。王老师并不想再也没法淘汰学生，因为这是他最大的爱好，所以在走之前他想知道班上至少要有多少学生，他才不会被开除。

输入格式

第一行一个数 T，表示 T 组数据。
对于每组数据，第一行两个整数 R 和 C。接下来 R 行，每行 C 个整数。从上到下是 1~R 行，
从左到右是 1~C 列。若 Sij < 0 则王老师会淘汰学生，否则加入学生。

输出格式

对于每组数据输出一行，想要能从(1, 1)走到(R, C)，王老师的班级需要在(1, 1)拥有的最小学生数。

样例输入

3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0

样例输出

2
1
2

数据范围

1 <= T <= 5；
2 <= R, C <= 500；
-10^3 <= Sij <= 10^3；
S11 = SRC = 0。

限制

2s

样例解释

对于第 1 组数据：
如果王老师在(1, 1)的学生数为1，那么他怎么走中间都会被开除，所以在(1, 1)他需要2个学生。
对于第 2 组数据：
从(1, 1)开始他需要最少 1 个学生。

来源

CWOI新高二专题测试二