Problem A. Kakuro

Game Rules

• Fill the empty cells with positive integers.
• In cells divided by a diagonal line, the number in the upper-right corner equals the sum of the numbers in the contiguous empty cells to its right, and the number in the lower-left corner equals the sum of the numbers in the contiguous empty cells below it.

Apia gave Rimbaud a Kakuro puzzle. Being clumsy, Rimbaud does not know how to solve Kakuro, so she just filled some random numbers into the empty cells, calling this a "state," which includes both the initial clues and the numbers she filled in.

Now, Rimbaud wants to modify this state so that her answer is a valid solution. Some numbers in this state (including the initial clues and the numbers she filled in) can be modified. Each number has a specific cost; changing a number by $+1$ or $-1$ incurs the corresponding cost for that number. Note that for a valid solution, the game rules must be satisfied, meaning the numbers in the empty cells must be positive integers and satisfy the sum conditions, but they are not required to be distinct.

Rimbaud wants to make the state valid with the minimum total cost. If it is impossible, output $-1$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of rows and columns of the game.

The next $n$ lines each contain $m$ integers from $0$ to $4$, where the $j$-th number in the $i$-th row represents the type of the cell at row $i$, column $j$: $0$ means the cell is neither an empty cell nor a clue. $1$ means the cell contains a clue in the lower-left corner and no clue in the upper-right corner. $2$ means the cell contains a clue in the upper-right corner and no clue in the lower-left corner. $3$ means the cell contains clues in both the lower-left and upper-right corners. * $4$ means the cell is an empty cell.

The input is guaranteed to be a valid Kakuro puzzle in terms of format, meaning every contiguous segment of empty cells has a clue in the cell to its left or above it.

The next $n$ lines each contain several positive integers, providing the initial numbers in the state from left to right. Specifically, if the cell type is $3$, the lower-left clue is given first, followed by the upper-right clue.

The next $n$ lines each contain several integers, providing the cost for each corresponding number in the initial state from left to right. If the cost is $-1$, it means the cell cannot be modified; otherwise, the cost is a non-negative integer. Note that the two clues in a type $3$ cell have two different costs.

Example 1 provides the input for the puzzle shown above. Please read Example 1 before solving to ensure you understand the input format.

Output

Output a single integer representing the minimum cost. If it is impossible, output $-1$.

Examples

Input 1

8 8
0 1 1 0 0 1 1 1
2 4 4 0 3 4 4 4
2 4 4 3 4 4 4 4
2 4 4 4 4 4 1 0
0 2 4 4 3 4 4 1
0 1 3 4 4 4 4 4
2 4 4 4 4 2 4 4
2 4 4 4 0 2 4 4
23 30 27 12 16
16 9 7 17 24 8 7 9
17 8 9 15 29 8 9 5 7
35 6 8 5 9 7 12
7 6 1 7 8 2 6 7
11 10 16 4 6 1 3 2
21 8 9 3 1 5 1 4
6 3 1 2 3 2 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1

Output 1

0

Input 2

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

Output 2

822

Constraints

• For 5% of the data, all costs are guaranteed to be $-1$.
• For 20% of the data, all costs for numbers in empty cells are guaranteed to be $-1$.
• For another 30% of the data, all costs for numbers representing clues are guaranteed to be $-1$.
• For another 20% of the data, only the first row and first column contain clues, and all other cells are empty cells.
• For 100% of the data, $3 \le n, m \le 30$, each number in the initial state does not exceed $10^6$, and the cost for each number does not exceed $10^6$.

Figure 1. The Kakuro puzzle grid for Example 1.