21692_FlowsinGrid

The maximum flow problem in general graph is so hard that bob doesn't know how to solve it. So bob want 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 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?

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¹⁰.

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

Here is one of the maximum flows of the example grid above: