Grid Network

Jaehyun runs a grid network consulting company. Given a company's data servers as a grid-shaped graph, he wants to install a dedicated communication network at minimum cost. In this network, any two servers must be able to communicate. Two servers do not need a direct connection; they may communicate through other servers.

The servers form a grid with R rows and C columns. A direct communication line can be installed between servers adjacent up, down, left, or right. The cost of installing a direct line is one of 1, 2, 3, 4. The costs have an interesting property: for a server A with adjacent servers B and C, the cost of installing a line between A and B never equals the cost of installing a line between A and C.

(a)	(b)
(c)	(d)

Figure (a) shows six servers and the cost of each communication line that can be installed between them. Figure (b) is not given as input, because the servers at (1, 2) and (2, 2) have two lines with the same cost.

For the grid network in figure (a), installing five lines lets any two servers communicate, and the minimum cost is 9. There are two ways to achieve the minimum, shown by the red lines in figures (c) and (d).

Given a grid network and the installation costs of the communication lines, find the minimum cost that lets any two servers communicate.

The first line gives the number of test cases T.

The first line of each test case gives R and C, separated by a space. The next R lines each contain C-1 integers, which represent the costs of installing communication lines that connect the C servers in each row horizontally. The next R-1 lines each contain C integers, which represent the costs of installing communication lines that connect the C servers in row i and row i+1 vertically.

For each test case, print the minimum cost on its own line.

• 1 ≤ T ≤ 10
• 2 ≤ R, C ≤ 500
• 1 ≤ cost of each line ≤ 4