文理学院程序设计在线练习


运果

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 29   Accepted Submission(s): 14
Problem Description

猴子们采摘了无数的桃子和苹果,想要运回仓库中。采摘到的果子放在一个大矩形区域的各个小矩形区域中。事先猴子们在矩形区域的左边和上方修好了两个仓库,可分别存放桃子、苹果。现在要把桃子运到桃子仓库中,把苹果运到苹果仓库中,于是修铁路的工作开始了。但猴子国的铁路工程师不够聪明,只会修直的铁路。而且向左和向上的铁路不能同时经过一个小矩形区域,否则要发生交通事故的。当然,铁路可以修若干条。而运果子时,火车所经过的小矩形区域中的相应果子都能被装上车运回去,而另一类果子只能放弃。向左修的铁路上的火车只能运桃子,向上修的铁路上的火车只能运苹果。现在要把尽可能多的果子运到两个仓库中去,请你帮助铁路工程师设计修路方案。


Input

测试数据有多组,先输入测试组数t。然后输入t组测试数据,每组测试的第一行是两个整数m和n(1 ≤ m,n ≤ 500 ),表示大矩形区域中的有m*n个小矩形区域,然后是两个m*n的矩阵,分别表示一个大矩形区域中各个小矩形区域中的桃子数量和苹果数量(都在0到1000范围内)。

Output

对于每组测试,在一行上输出能运回到两个仓库中果子总数s。

Sample Input
1
4 4
0 0 10 9
1 3 10 0
4 2 1 3 
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
Sample Output
98
Source

2011校计算机技能竞赛