Contest02-6 Flows in Grid

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

The maximum flow problem in general graph is so hard that bob doesn't know how to solve it. So bob wants to try an easy one, the maximum flow in grid. But this easier one is still too hard for bob. Now here is his problem, please help him:

Given you a N*M grid as followed, edges of the grid represent pipes which the water can run through; the number of the edge is the capacity of the pipe. For example in Figurn 1 the capacity of the edge between (0,0) and (1,0) is 6, it means that at most 6 units of water can run through this edge(pipe). So what is the maximum flow from S to T in the grid? In other words, at most how many units of water can run through from S to T at a time?

Input

The first line of the input is a positive integer T. T is the number of the test cases followed.

The first line of each test case is two positive integers N(1 < N < 100)and M(1 < M < 100). And then two integer matrices H(N*(M-1)) and V((N-1)*M) follow. H[i][j] is the capacity of the edge between(i,j) and (i,j+1). V[i][j] is the capacity of the edge between (i,j) and (i+1,j). All integers in H and V are non-negative and smaller than 10^10.

Output

The output of each test case is an integer in one line, the maximum flow of the grid between S(0,0) and T(N-1,M-1). No redundant spaces are needed.

1
3 3
0 1
2 3
4 5
6 7 8
9 10 11

6

Hint

Figure 2 is one of the maximum flows of the example grid above: ZSCPC9