思路

• 设 $need[i][j]$ 表示“到达 $(i,j)$ 这一刻之前必须至少有多少积分”，这样在加上当前格子 $a_{ij}$ 后，仍能保证后续一路存活并最终到达终点，同时过程中积分始终 $>0$。

• 终点处有

  $$need[N][M]=\max{1,1-a_{N,M}}$$

  因为到达终点后不再前进，但本格加上后仍需保持积分 $\ge 1$。

题目内容

这是一个经典的 $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$ 个数字 $a_{ij}(-1000<=a_{ij}<=1000)$，代表题目所描述的 $N$ 行 $M$ 列的二维迷宫中每个格子对应的整数。

输出描述

输出 $T$ 行，每行 $1$ 个整数，代表 $T$ 组输入数据对应的答案。

样例1

输入

1
2 3
0 1 -3
1 -2 0

输出

2

说明

如果玩家初始积分为$1$，那不管怎么走都会在迷宫中间输掉游戏，所以最少需要$2$个积分