Orchard

Interview

Time limit2sMemory limit512 MB

Summary

Pick one rectangle for Bert to minimize the bananas left outside it plus the apples inside it.

Level: Medium6 of 10
Topics: Matrix, Prefix sum, Dynamic programming
Solved: No attempts yet

Problem

Alex and Bert planted apple trees (0) and banana trees (1) in an $n \times m$ orchard. Each cell has one tree type, and each brother planted at least one tree.

Their uncle first gives the whole orchard to Alex. Alex and Bert then choose one rectangular region to transfer to Bert. They do not replant; any remaining mismatch is fixed by paid ownership transfers at $1 per tree.

Alex wants only apples and Bert wants only bananas. Find the minimum transfer fee after choosing the best rectangle.

Input

Line 1: $n$ , $m$ .

Next $n$ lines: $m$ values each, 0 for apple and 1 for banana.

Output

Print the minimum fee.

Examples6

Example 1

Input

5 7
0 0 1 0 0 1 0
0 1 1 1 1 1 0
0 1 1 0 0 1 0
0 1 1 1 1 1 0
0 0 1 0 0 1 0

Expected output

Example 2
Input
```
2 2
0 1
1 0
```
Expected output
```
1
```
Example 3
Input
```
2 1
0
1
```
Expected output
```
0
```
Example 4
Input
```
2 3
1 1 1
1 1 1
```
Expected output
```
0
```
Example 5
Input
```
2 2
0 0
0 0
```
Expected output
```
0
```
Example 6
Input
```
3 3
0 1 0
1 0 1
0 1 0
```
Expected output
```
3
```