Description

Rules of this problem: • Fill each blank with a positive integer. • In a square divided by a diagonal, the number in the upper-right corner equals the sum of the numbers in the contiguous squares to its right, and the number in the lower-left corner equals the sum of the numbers in the contiguous squares below it.

Apia gave Rimbaud a Kakuro puzzle. Clumsy as she is, Rimbaud did not know how to solve Kakuro, so she filled some random numbers into the blanks. We call this a position: it includes both the initially given clues and the numbers filled later.

Now Rimbaud wants to modify this position so that her answer becomes a valid solution. Some numbers in this position (including both the initially given clues and the numbers filled later) can be modified. Each number has a specific cost: increasing or decreasing this number by 1 costs its associated cost per unit. Note that any valid solution must satisfy the game rules: the numbers filled in blanks must be positive integers and must satisfy the sum conditions, but distinctness is not required.

Rimbaud wants to make the position valid with the minimum total cost; if impossible, output -1.

Input Format

The first line contains two positive integers n, m, the numbers of rows and columns.

Then follow n lines, each containing m integers from 0 to 4; the integer in row i and column j denotes the type of the cell at (i, j): • 0 means the cell is neither a blank nor a clue. • 1 means the cell has a clue in the lower-left corner, and no clue in the upper-right corner. • 2 means the cell has a clue in the upper-right corner, and no clue in the lower-left corner. • 3 means the cell has clues in both the lower-left and upper-right corners. • 4 means the cell is a blank.

The input is guaranteed to be a syntactically valid Kakuro puzzle: for every contiguous run of blanks, the cell immediately to its left or immediately above contains a clue.

Then follow n lines, each containing a sequence of positive integers, giving, from left to right, every number present in the initial position. In particular, if a cell is of type 3, then the lower-left clue is given first, followed by the upper-right clue.

Then follow n lines, each containing a sequence of integers, giving, from left to right, the modification cost corresponding to each number in the initial position. A cost of -1 means the number in that cell cannot be modified; otherwise the cost is a nonnegative integer. Note that the two clues in a type 3 cell have two different costs.

Sample 1 gives the input for the puzzle above. Please read Sample 1 before solving to ensure you understand the input format.

Output Format

Output a single integer, the minimum total cost. If it is impossible, output -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

0

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

822

Hint

• For 5% of the testdata, all costs are -1. • For 20% of the testdata, the costs of all numbers in blanks are -1. • For another 30% of the testdata, the costs of all clue numbers are -1. • For another 20% of the testdata, only the cell at row 1, column 1 contains clues, and all remaining cells are blanks. • For 100% of the testdata, 3 ≤ n, m ≤ 30, every number in the initial position is at most $10^6$, and every cost is at most $10^6$.

Translated by ChatGPT 5