Largest Rectangle

Time limit0.6sMemory limit128 MB

Summary

Given a binary matrix where columns may be freely reordered, find the maximum area rectangle of all-1 cells after computing per-cell run heights and sorting rows to combine widths.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting, Matrix
Solved: No attempts yet

Problem

You are given an N × M matrix consisting of 0s and 1s. Write a program that finds the area of the largest rectangle whose cells are all 1. You may freely rearrange the order of the columns; that is, you may pick some columns, place them next to one another in any order, and if every cell of those columns over some range of consecutive rows is 1, they form a rectangle. (The order of the rows cannot be changed.)

Input

The first line contains two integers N and M separated by a space. Each of the next N lines contains a string of length M consisting of 0s and 1s, describing the matrix.

Output

Print the area of the largest all-ones rectangle on the first line.

Constraints

1 ≤ N ≤ 15000
1 ≤ M ≤ 1500

Hint

By reordering the columns so that the 2nd, 4th, and 5th columns are adjacent, you can obtain a rectangle of area 21 (rows 2 ~ 8 × columns 2, 4, 5).

Examples5

Example 1

Input

Expected output

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