cyk的游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

最近,智商频繁下线的 cyk 迷上了一个益智小游戏,每天都要玩到深夜,乐此不疲。

 

这个游戏的规则是这样的:

玩家控制一个游戏角色 cyk0 站在一个 n*m 的矩形格子地图上,每个格子都可以提供一定的智力值加成。

初始时 cyk0 位于左上角 (1, 1),游戏的目标是通过走若干步到达位于右下角 (n, m) 的智慧长者 cyk4 处。

沿途走到的格子可以增加相应的智力,到达终点时累积获得的智力就是游戏的得分。

普通玩家的角色每回合只能向右移动或向下移动一次,移动距离为一格。而 VIP 玩家可以在移动角色时选择是否使用主动技能「yk 大冲刺」。「yk 大冲刺」的效果是:使当前回合的移动距离扩大为地图尺寸的一半(向右移动时可以扩大为 m/2,向下移动时可以扩大为 n/2)。此技能是直接移动,中间经过的格子不累计智力值,而且不能越出地图边界,否则本次移动无效。VIP 技能每个回合只能施放一次。

 

虽然最近 cyk 购买了 VIP,不过他实在是太忙了,每天在实验室待到很晚,并没有太多时间去思考如何才能得到最高分。你能帮助他拿到最高分吗?

Input

第一行输入一个整数 T (0 < T <= 20),代表数据组数。

对于每组输入,首先输入一行,包含两个整数 n, m (0 < n, m <= 1000),表示地图的行数和列数,保证 n, m 不会是奇数。

接下来输入 n 行,每行 m 个以空格分隔的整数 ai (-10^7 <= ai <= 10^7),表示此格子上可提供的智力值。

Output

对于每组输入,输出一行,包含一个整数,代表 cyk 能得到的最高分。

Sample Input

2
2 4
1 3 10 8
2 1 2 0
4 4
1 5 3 15
-3 -5 -4 -1
2 4 0 3
9 12 1 6

Sample Output

22
33

Hint

Source

【第八届山东理工大学ACM网络编程擂台赛 热身赛】cyk2 (bLue)