Chessboard Game: Optimal Move Score Difference

Two players, Feifei and Niuniu, play a game on an \( n \)-row, \( m \)-column chessboard. Feifei (playing with black pieces) moves first, and Niuniu (with white pieces) moves second. Initially, the board is empty. They take turns placing pieces on the board until every cell is filled.

The rule for placing a piece is: A piece can be placed in cell \( (i,j) \) if and only if the cell is empty and every cell to its left (in the same row) and every cell above (in the same column) already contains a piece. In other words, for cell \( (i,j) \) the condition is that all cells \( (i,k) \) for \( k<j \) and \( (l,j) \) for \( l<i \) are already occupied.

Every cell \( (i,j) \) on the board has two nonnegative integers written on it: \( a_{i,j} \) and \( b_{i,j} \). In the final board, Feifei's (Black's) score is the sum of \( a_{i,j} \) over all cells occupied by a black piece, and Niuniu's (White's) score is the sum of \( b_{i,j} \) over all cells occupied by a white piece.

Both players want to maximize the difference between their own score and their opponent's score. Assuming both players play optimally, what will the final score difference be (calculated as Feifei's score minus Niuniu's score)?

Note: The cell \( (1,1) \) is forced as the first move by Feifei. After that, the state of the board always forms a filled rectangle in the upper-left corner. If the current filled rectangle extends to \( (i,j) \), the only possible moves are to fill cell \( (i, j+1) \) (if \( j < m \)) or cell \( (i+1, j) \) (if \( i < n \)). When a player chooses a move, their immediate gain is either \( a_{i,j+1} \) (or \( a_{i+1,j} \)) if Feifei plays, or \( -b_{i,j+1} \) (or \( -b_{i+1,j} \)) if Niuniu plays, and then the opponent moves. The final answer is \( a_{1,1} + \text{dp}(1,1, white) \), where \( \text{dp}(i,j,turn) \) is determined by the optimal minimax strategy.

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns).

The next \( n \) lines each contain \( m \) integers, representing the matrix \( a \) where the \( j \)-th integer in the \( i \)-th line is \( a_{i,j} \).

The following \( n \) lines each contain \( m \) integers, representing the matrix \( b \) where the \( j \)-th integer in the \( i \)-th line is \( b_{i,j} \).

outputFormat

Output a single integer: the final score difference (Feifei's score minus Niuniu's score) if both players play optimally.

sample

2 2
1 2
3 4
0 1
2 1

3