Description

小桂同学近期自己开发了一个小游戏$——Pac-Man$。

游戏是这样的：在一个$n*m$的矩形游戏平台上，$Pac-Man$会随机出生在一个位置，除了$Pac-Man$出生的位置之外，这个矩形的游戏平台上的每个位置都会有一个豆子，$Pac-Man$吃掉每颗豆子将会获得不同的分数，豆子被吃掉后就会消失。玩家可以操作$Pac-Man$向上、下、左、右四个方向进行移动，玩家的任务是操作$Pac-Man$移动，并且尽可能得夺得高分。

小桂同学觉得这个游戏太简单了，所以他给自己增加了操作限制$——$除了最开始的方向选择外，只能改变一次前进方向。现在小桂同学想知道，对于一局游戏，他能够获得的最高分数是多少？

Input Format

第一行输入一个正整数$t(1\le t\le100)$，表示有$t$组测试样例。

接下来对于每组测试样例，首先输入两个正整数$n,m(1 \le n,m \le100)$，表示游戏平台的大小。接着输入$n$行，每行$m$个正整数$ai(1\le ai\le100)$，表示吃掉这个位置的豆子将会获得的分数。特殊的，我们用$-1$来表示$Pac-Man$在游戏界面的出生位置（题目保证每组测试样例有且只有一个$-1$）。

Output Format

对于每组测试样例，输出一行，表示对于该组样例能够获得的最高的游戏分数。

1
3 4
4 5 2 1
2 1 -1 2
3 3 2 1

11

Hint

首先小桂同学初始选择向上方移动，走到底后我转一直走到地图边界。

这样小桂同学可以获得的分数为：$2+5+4 = 11$。如此选择为最优，因此答案为$11$。

如图，粉色箭头表示前进路线。

Source

Online Judge http://127.0.0.1