P3604.第2题-迷宫速通
题目内容
这是一个经典的 N 行 M 列的二维迷官，每个格子有一个整数，代表这个格子的“奖励”或“惩罚”。
玩家从最左上角的格子 (1,1) 出发，目的地是最右下角的格子 (N,M)，并且玩家只能向右或向下走玩家在游戏开始时积分为 0 ，并且每到一个格子(包括起始位置和终点位置)，都需要把当前积分加上这个格子对应的整数(显然，若整数为正就是“奖励”，若为负就是“惩罚”)。当玩家在任意时刻积分为 0 或负数时，就输掉了游戏。
马老师是玩迷宫速通的老玩家，他想到：如果格子 (1,1) 对应的整数是负数，就会在游戏一开始就直接输掉游戏，有辱他的一世英名。幸好，马老师具有高超的编程技巧，一眼就能看出如果他使用黑客技术把玩家初始积分设置为 x ，就可以通过游戏。
聪明的马老师想考考你，x 最小可以是多少。
输入描述
第一行有 1 个整数 T(1<=T<=5) ,代表数据的组数。
接下来一共是 T 组数据，对于每组数据：
第一行包含两个正整数 N 和 M(1<=N,M<=500) 。
接下来 N 行，每行包含 M 个数字 aij(−1000<=aij<=1000)，代表题目所描述的 N 行 M 列的二维迷宫中每个格子对应的整数。
输出描述
输出 T 行，每行 1 个整数，代表 T 组输入数据对应的答案。
样例1
输入
1
2 3
0 1 -3
1 -2 0
输出
2
说明
如果玩家初始积分为1，那不管怎么走都会在迷宫中间输掉游戏，所以最少需要2个积分
