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

23597: 小猴子的难题(一)

时间限制: 1 Sec  内存限制: 64 MB
提交: 106  解决: 28
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

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



输入

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

输出

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

样例输入

1
2 3
0 6 2
4 5 6

样例输出

17

提示

from:lovychen

来源

[提交][状态]