| 2020 ICPC Asia East Continent Final |
|---|
| Finished |
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.
- Either 0 or 2 tubes connected to each crossing are used.
- 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 ai, j to use the tube connecting crossings (i, j) and (i, j + 1). It costs bi, 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 ≤ 109) separated by single spaces.
The i-th of the following n lines contains m + 1 integers 
(1 ≤ {b}i, j ≤ 109) 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 104.
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
