Background

First, let's introduce the game of Kakuro (カックロ).

The rules of the game are:

• Numbers from 1 to 9 are filled in the square cells.
• In cells divided by a slash, the number in the top right corner equals the sum of the numbers in the consecutive cells to its right, and the number in the bottom left corner equals the sum of the numbers in the consecutive cells below it.
• Numbers in consecutive cells cannot repeat, whether horizontally or vertically.

The left image is a Kakuro puzzle, and the right image is its unique solution.

We call the initially given numbers clues, and the places where numbers need to be filled empty cells. If a cell contains a clue, it does not need to be filled. We stipulate that all puzzles are non-empty, meaning at least one empty cell needs to be filled.

Note: The game rules in the following problems may differ, so please read the rules under each problem carefully.

Problem Description

Game rules:

• Positive integers are filled in the empty cells.
• In cells divided by a slash, the number in the top right corner equals the sum of the numbers in the consecutive cells to its right, and the number in the bottom left corner equals the sum of the numbers in the consecutive cells below it.

Apia gave Rimbaud a Kakuro puzzle. Inept at solving Kakuro, Rimbaud filled some random numbers in the empty cells, calling this a situation, which includes the initial clues and the numbers filled later.

Now, Rimbaud wants to modify this situation to make her answer a valid solution. Some numbers (including the initial clues and the filled numbers) in this situation can be modified. Each number has a specific cost, and increasing or decreasing this number by 1 incurs the corresponding cost. Note that for a valid solution, the rules of the game must be satisfied, meaning the numbers filled in the empty cells must be positive integers and meet the sum conditions, but repetition is not required.

Rimbaud hopes to make this situation valid with the least cost, or output -1 if it is impossible.

Input Format

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

The next n lines contain m numbers from 0 to 4 each, where the number at the i-th row and j-th column represents the type of the cell at the i-th row and j-th column.

• 0 means this cell is neither an empty cell nor a clue.
• 1 means this cell has a clue in the bottom left corner and no clue in the top right corner.
• 2 means this cell has a clue in the top right corner and no clue in the bottom left corner.
• 3 means this cell has clues in both the top right and bottom left corners.
• 4 means this cell is an empty cell.

The input guarantees that the puzzle is a valid Kakuro puzzle in terms of format, meaning each segment of consecutive empty cells has a clue to its left or above.

The next n lines contain several positive integers, giving the numbers in the initial situation from left to right. Specifically, if the cell type is 3, the clue in the bottom left corner is given first, followed by the clue in the top right corner.

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

Please read Sample Input 1 before solving the problem to ensure you understand the input format.

Output Format

An integer representing the minimum cost, or -1 if it is impossible.

Sample Input and Output

Input Sample #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 Sample #1

0

Input Sample #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 Sample #2

822

Notes/Hints

For 5% of the data, all costs are guaranteed to be -1.

For 20% of the data, the costs of all numbers in the empty cells are guaranteed to be -1.

For another 30% of the data, the costs of all clue numbers are guaranteed to be -1.

For another 20% of the data, only the first row and first column contain clues, and the rest are empty cells.

For 100% of the data, it is guaranteed that 3 ≤ n, m ≤ 30, the initial numbers in the situation do not exceed $10^6$, and the costs of each number do not exceed $10^6$.

见题面 Input 部分

见题面 Output 部分