D : 探 寻 宝 藏

Progress Bar

时间限制:1 Sec 内存限制:128 MiB
提交:40 答案正确:25

提交


题目描述

传说HMH大沙漠中有一个M*N迷宫,里面藏有许多宝物。某天,Dr.Kong找到了迷宫的地图,他发现迷宫内处处有宝物,最珍贵的宝物就藏在右下角,迷宫的进出口在左上角。当然,迷宫中的通路不是平坦的,到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。

但机器人卡多从左上角走到右下角时,只会向下走或者向右走。从右下角往回走到左上角时,只会向上走或者向左走,而且卡多不走回头路。(即:一个点最多经过一次)。当然卡多顺手也拿走沿路的每个宝物。

Dr.Kong希望他的机器人卡多尽量多地带出宝物。请你编写程序,帮助Dr.Kong计算一下,卡多最多能带出多少宝物。

输入

第一行: K     表示有多少组测试数据。 

接下来对每组测试数据:

1:       M   N

2~M+1行: Ai1  Ai2 ……AiN    (i=1,..,m)

2k5      1M, N50     0Aij100    (i=1,.,M; j=1,,N)

所有数据都是整数。 数据之间有一个空格。

输出

对于每组测试数据,输出一行:机器人卡多携带出最多价值的宝物数

样例输入

复制
2
2 3
0 10 10
10 10 80
3 3
0 3 9
2 8 5
5 7 100

样例输出

复制
120
134

提示


			

来源

河南省第六届大学生程序设计竞赛