408251: GYM103069 E Tube Master III

Prof. Pang is playing "Tube Master". The game field is divided into n × m cells by (n + 1) × m horizontal tubes and n × (m + 1) vertical tubes. The product nm is an even number. There are (n + 1)(m + 1) crossings of the tubes. The 2D coordinate of the crossings are (i, j) (1 ≤ i ≤ n + 1, 1 ≤ j ≤ m + 1). We name the crossing with coordinate (i, j) as "crossing (i, j)". We name the cell whose corners are crossings (i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1) as "cell (i, j)" for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. Additionally, each cell (i, j) contains an integer {count}_i, j.

The above figure shows a game field with n = 3, m = 2 (the third sample).

Prof. Pang decides to use some of the tubes. However, the game poses several weird restrictions.

1. Either 0 or 2 tubes connected to each crossing are used.
2. There are exactly {count}_i, j turning points adjacent to cell (i, j). A turning point is a crossing such that exactly 1 horizontal tube and exactly 1 vertical tube connected to it are used. A turning point (x, y) is adjacent to cell (i, j) if crossing (x, y) is a corner of cell (i, j).

It costs a_i, j to use the tube connecting crossings (i, j) and (i, j + 1). It costs b_i, j to use the tube connecting crossings (i, j) and (i + 1, j). Please help Prof. Pang to find out which tubes he should use such that the restrictions are satisfied and the total cost is minimized.

The first line contains a single positive integer T denoting the number of test cases.

For each test case, the first line contains two integers n, m (1 ≤ n, m ≤ 100) separated by a single space.

The i-th of the following n lines contains m integers {count}_i, 1, {count}_i, 2, ..., {count}_i, m (0 ≤ {count}_i, j ≤ 4) separated by single spaces.

The i-th of the following n + 1 lines contains m integers {a}_i, 1, {a}_i, 2, ..., {a}_i, m (1 ≤ {a}_i, j ≤ 10⁹) separated by single spaces.

The i-th of the following n lines contains m + 1 integers (1 ≤ {b}_i, j ≤ 10⁹) separated by single spaces.

It is guaranteed that nm is an even number and that the total sum of nm over all test cases does not exceed 10⁴.

For each test case, output an integer that denotes the minimum cost. If there is no valid configuration, output "-1" instead.

4
2 3
4 3 2
2 3 4
2 1 1
2 1 2
1 2 1
1 2 1 2
1 1 1 2
2 2
2 1
2 1
1 2
2 2
1 2
1 2 1
2 1 1
3 2
1 2
3 3
3 2
1 1
1 1
2 2
1 1
1 1 1
1 1 1
2 2 2
2 2
1 2
3 4
5 6
7 8
9 10
11 12 13
14 15 16

13
8
11
-1