Description

By chance, a magician came to Magic Land and, upon leaving, left behind a mysterious box called the Casket of Star.

Although its purpose is unknown, after extensive experiments and calculations, people have learned some facts about it:

1. Inside the Casket of Star there are $N\times M$ regions, which can be viewed as a grid with $N$ rows and $M$ columns. Each region contains some integer number of objects called “stars.” Since the smallest unit has been determined, this quantity is always an integer.
2. The magician can drive $1$ unit of “star” in each of two non-adjacent regions that lie in the same row or the same column (regions sharing a common edge are considered adjacent), making them each move $1$ cell toward the center.
3. Each time the operation in 2 is used to drive the “stars,” magic power is generated, which the magician receives. The amount of magic power equals the number of regions lying strictly between those two regions.

Thus, we can represent a state of the Casket of Star by an $N\times M$ table. For example, when $N=2, M=3$:

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

When the Casket of Star is in the state on the left, by operating on the “stars” in the 1st and 3rd regions of the first row, it becomes the state on the right, while generating $1$ unit of magic power (because exactly $1$ region lies between those two regions).

After further research, people have determined the initial state (Ini) and the final state (Fin) at the time they obtained it.

You want to know the maximum amount of magic power the Casket of Star could have provided its owner. That is, over a sequence of the above operations that transforms the initial state (Ini) into the final state (Fin), what is the maximum total magic power that can be generated?

Note that, obviously, during the operations the number of “stars” in any region cannot become negative. If a region already has no “stars,” you cannot continue operating on it.

Input Format

The first line contains two positive integers $N, M$, indicating the size of the Casket of Star.

The next $N$ lines each contain $M$ non-negative integers: $\mathit{Ini}_{i,j}$, describing the initial state (Ini).

After a blank line, the next $N$ lines each contain $M$ non-negative integers: $\mathit{Fin}_{i,j}$, describing the final state (Fin).

Output Format

Output a positive integer, the maximum total magic power that can be generated.

5 5 
1 0 0 0 1 
0 0 0 0 0 
0 0 0 0 0 
0 1 0 1 1 
1 0 0 0 0 

0 0 0 0 0 
0 0 0 0 1 
2 0 0 0 1 
0 0 2 0 0 
0 0 0 0 0

7

Hint

For $100\%$ of the testdata, $1\le N, M\le 200$, and $\mathit{Ini}_{i,j}, \mathit{Fin}_{i,j}\le 1000$.

All testdata guarantee that there exists at least one sequence of operations transforming the Casket of Star from the initial state to the final state, and also guarantee that the initial and final states are not identical.

Translated by ChatGPT 5