One is Good, but Two is Better

Time limit1sMemory limit128 MB

Summary

Given an N by M grid of 0, 1, and 2, cover every 2 with two rectangles that avoid 1, minimizing the total area covered.

Level: Medium7 of 10
Topics: Brute force, Prefix sum, Matrix, Greedy
Solved: No attempts yet

Problem

You are given an $N \times M$ matrix whose entries are each $0$ , $1$ , or $2$ . At least one entry equals $2$ .

Choose two axis-aligned rectangles (they may overlap, and they may even be identical) so that:

every cell equal to $2$ lies inside at least one of the two rectangles, and
neither rectangle contains any cell equal to $1$ (cells equal to $0$ are allowed inside a rectangle).

The area of a rectangle is the number of cells it covers. Among all valid choices, minimize the area of the region covered by the two rectangles together (a cell covered by both rectangles is counted once).

Report that minimum combined area, or report that no valid pair of rectangles exists.

Input

The first line contains two integers $N$ and $M$ . Each of the next $N$ lines contains $M$ integers, giving the matrix row by row; every value is $0$ , $1$ , or $2$ .

Output

Print a single integer: the minimum combined area of the two rectangles, or $-1$ if no valid pair exists.

Constraints

$1 \le N, M \le 50$
Every matrix entry is $0$ , $1$ , or $2$ .
At least one entry equals $2$ .

Examples4

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