Casket of Star – Maximum Magic Generation

A mysterious magician left behind a magical box called the Casket of Star which is divided into N×M cells. In each cell there is an integer number of "star" units. After many experiments, people have learned that one can use the magic:

• At any time, you may pick two cells in the same row or in the same column that are not adjacent (two cells sharing a common edge are considered adjacent) and, from each, remove exactly 1 star (provided that cell has at least one star). Then, each star moves one cell toward the center (i.e. the left one moves one cell to the right, or the top one moves one cell down; similarly, the right one moves one cell to the left, and the bottom one moves one cell up).
• This operation generates magic. The amount of magic produced equals the number of cells between the two cells selected. For example, if you choose two cells in the same row at positions i and j (with j − i > 1) then the magic generated is j − i − 1.

You are given the initial configuration Ini and the final configuration Fin of the casket (each an N×M grid of nonnegative integers). Note that in any legal operation the number of stars in any cell must never become negative. Moreover, because a row‐(or column–)move only redistributes stars within that row (or column), the two configurations have the same row sums and the same column sums.

Your task is to determine the maximum total magic that can possibly be generated when transforming Ini to Fin via a sequence of legal operations.

Achieving Maximum Magic:

The key is that an operation (in a row or column) produces magic only if the two cells chosen are not adjacent. In an optimal strategy, one may combine multiple operations so that stars originally located far apart are paired in moves. In fact, one may show that the maximum magic obtainable is determined independently for each row and for each column. For a given row the following process achieves the optimal result:

• For each cell in the row, compute diff = Ini[i] − Fin[i].
• Note that a positive diff indicates that a cell originally contains more stars than in the final configuration. Since the moves always take 1 star from a cell, these extra stars may be thought of as suppliers. Because moves always take two stars (from two different cells) and move them inward, magic is only produced when two extra (surplus) stars from cells that are not adjacent are paired.
• Imagine listing, for that row, the cell indices of all surplus stars (each cell i appears exactly diff times if diff > 0). Then, by pairing the leftmost surplus with the rightmost surplus, the magic produced by that pair will be (j − i − 1) (if the two indices are i and j with i < j). Removing these two units from the pool, one continues pairing the smallest remaining index with the largest remaining index. (If there is an odd number of surplus stars, one unit is left unpaired.)

Apply the analogous procedure to each column. The final answer is the sum of the magic from all rows and all columns.

Note: It is guaranteed that the input is such that Ini can be transformed into Fin by a sequence of legal moves (i.e. the row sums and column sums of the two configurations are identical).

inputFormat

The first line contains two integers N and M (1 ≤ N, M ≤ 100), the number of rows and columns.

The next N lines each contain M nonnegative integers representing the initial configuration Ini.

This is followed by N lines each containing M nonnegative integers representing the final configuration Fin.

It is guaranteed that for every row the sum of the numbers in Ini equals the sum for Fin and for every column the sum in Ini equals the sum in Fin.

outputFormat

Output a single integer — the maximum total magic that can be generated when transforming Ini into Fin by a sequence of legal moves.

sample

2 3
2 0 1
5 1 4
1 2 0
5 1 4

1