Problem 23597 --小猴子的难题(一)

23597: 小猴子的难题(一)

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 106  Solved: 28
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

话说孙悟空取经的途中曾遇到一座大山,大山上有很多宝藏,当然了,妖怪也是在所难免的,此山能大能小,最高不过50米,最宽嘛也不过40米而已,此山是通往西天取经的必经之路,山上有很多的宝藏,宝藏都位于洞穴之中,你路过洞穴,就能获得宝藏,当然了,你遇到妖怪之后还要上交过路费,当宝藏大于等于0的时候,你就能获得它,当少于0的时候,说明洞穴中存在妖怪,你要上交过路费了,宝藏最大不超过100块,不小于-100块;小猴子是打不过他们的,因为他没有了72变,你要想问为什么,这个、、、
PS:此时的你位于左山脚下,你的任务就是到达山顶最右端,并取得最大的价值,以供在以后的路上开销,此山特别的神奇,当你每上升一层的时候,你的下面就全部自动消失了,当你每向右走一层的时候,你的左面也全部自动消失了;



Input

输入:
开始先输入一个T,表示下面有T组数据;
接下来会有T行,每行有两个数x,y,分别表示山的高和山的宽;
接下来有x行,每行有y个数;第一行表示最上面一层,第二行最上面的下面一层、、、最后一行表示最底层;

Output

输出:输出有一组数据,表示猴子所能获得的最大的金钱数;

Sample Input

1
2 3
0 6 2
4 5 6

Sample Output

17

HINT

from:lovychen

Source

[Submit][Status]