Minimum Cost Kakuro Adjustment

You are given a Kakuro puzzle board composed of two types of cells: white cells and clue cells. In a white cell a positive integer must be filled. In a clue cell the cell is divided by a diagonal line into two parts. The number in the top‐right corner equals the sum of the contiguous white cells to its right, and the number in the bottom‐left corner equals the sum of the contiguous white cells below. The board is provided as an initial configuration (called a "state") in which every cell (both those that originally contained clues and those where an answer was filled in) has an integer. Each number in the board can be modified. However, increasing or decreasing a number by 1 incurs a cost that is specific to that cell.

Your task is to adjust the numbers in the board with the minimum total cost in order to transform the state into a valid Kakuro solution. A valid solution satisfies the following conditions:

• Every white cell must contain a positive integer (≥ 1).
• For every clue cell, if there is a horizontal (top‐right) clue then it must equal the sum of the contiguous white cells immediately to its right. Similarly, if there is a vertical (bottom‐left) clue then it must equal the sum of the contiguous white cells immediately below.

The board is given in a grid of r rows and c columns. In the input, each cell is represented as follows:

• If the cell is a white cell, it is represented by a single positive integer (its current filled value).
• If the cell is a clue cell, it is represented by two positive integers separated by a backslash (e.g. 5\7), where the first number is the horizontal clue (sum for white cells to the right) and the second number is the vertical clue (sum for white cells below).

In addition, a cost grid is provided that has the same dimensions as the board. The cost grid gives the cost required to modify the number in the corresponding cell by 1 (either increasing or decreasing by 1).

Your goal is to choose new numbers for each white cell (and consequently adjust the clues optimally so that they exactly equal the sums of the contiguous white cells) such that the total cost of all modifications is minimized. If it is impossible to obtain a valid configuration, output -1.

inputFormat

The input starts with two integers r and c (the number of rows and columns). This is followed by r lines, each containing c tokens that represent the board. Each token is either:

• A single positive integer if the cell is a white cell.
• A token in the format X\Y if the cell is a clue cell, where X is the horizontal clue and Y is the vertical clue.

After the board, there are r additional lines each containing c integers. These integers represent the cost grid; the cost at cell (i, j) is the cost incurred for increasing or decreasing the number in that cell by 1.

Example Input:

2 2
5\7 3
4 2
1 2
3 1

outputFormat

Output a single integer — the minimum total cost required to adjust the board into a valid solution. If it is impossible, output -1.

Example Output:

5

sample

2 2
5\7 3
4 2
1 2
3 1

5