B-Matrix

Interview

Time limit1sMemory limit128 MB

Summary

Find two non-overlapping all-zero rectangles in a binary grid maximizing the total number of cells they cover.

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

Problem

You are given an $m \times n$ binary matrix (each entry is 0 or 1). Choose two axis-aligned rectangles, each consisting only of 0s, so that the two rectangles do not overlap. Write a program that finds the maximum possible sum of their areas (the number of cells they cover).

Each rectangle is aligned to the grid cells, and every cell inside it must be 0.
The two rectangles must not share a single cell.
If there are not enough 0s, one of the rectangles may be empty (area 0).

Input

The first line contains two integers $m$ and $n$ separated by a space. ( $0 \le m, n \le 200$ )

Each of the next $m$ lines contains $n$ values (0 or 1) forming one row of the matrix.

Output

Print, on one line, the maximum total area that can be covered by two non-overlapping all-zero rectangles.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3 3
000
000
000
```
Expected output
```
9
```
Example 3
Input
```
3 7
0001000
0001000
0001000
```
Expected output
```
18
```