Feifei and Niuniu are playing a game on an $n \times m$ grid. Feifei plays with black pieces and goes first, while Niuniu plays with white pieces and goes second.

At the beginning of the game, the board is empty. The two players take turns placing pieces on the grid until the board is completely filled. The rule for placing a piece is: a piece can be placed in a cell if and only if the cell is currently empty and all cells to its left and above it are already occupied.

Each cell $(i, j)$ on the board (where $i$ is the row index and $j$ is the column index) has two non-negative integers associated with it, denoted as $A_{i,j}$ and $B_{i,j}$. After the game ends, Feifei and Niuniu calculate their respective scores: Feifei's score is the sum of $A_{i,j}$ for all cells containing a black piece, and Niuniu's score is the sum of $B_{i,j}$ for all cells containing a white piece.

Both Feifei and Niuniu want to maximize the difference between their own score and their opponent's score. Given the board, if both players play optimally and know that the other player will also play optimally, what will be the final result?

Input

The first line contains two positive integers $n$ and $m$, where $n, m \le 10$.

The next $n$ lines each contain $m$ non-negative integers, describing the first integer $A_{i,j}$ for each cell in row-major order.

The next $n$ lines each contain $m$ non-negative integers, describing the second integer $B_{i,j}$ for each cell in row-major order.

Output

Output a single integer representing the result of Feifei's score minus Niuniu's score.

Examples

Input 1

2 3
2 7 3
9 1 2
3 7 2
2 3 1

Output 1

2

Note

The board is shown below. When both players play optimally, the game proceeds as follows:

• Feifei places a piece at (1, 1) (this is the only available cell for the first move);
• Niuniu places a piece at (1, 2);
• Feifei places a piece at (2, 1);
• Niuniu places a piece at (1, 3);
• Feifei places a piece at (2, 2);
• Niuniu places a piece at (2, 3) (this is the only available cell for this move);
• The board is filled, and the game ends.

Feifei's score is: $2 + 9 + 1 = 12$; Niuniu's score is: $7 + 2 + 1 = 10$.

Input 2

(See chess/chess2.in in the contestant directory)

Output 2

(See chess/chess2.ans in the contestant directory)

Subtasks

For all test data, $n, m \le 10$ and $A_{i,j}, B_{i,j} \le 100000$. For test cases with odd numbers, it is guaranteed that all $B_{i,j} = 0$.