# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Puzzle of 1's and 0's

By mainstring · Limits 1s, 512 MB

There is a rectangular puzzle board containing $N \times M$number of places. Each place contains a number: either $1$ or $0$.

You are given P number of extra $2$’s. You can replace any of the numbers on the board with your extra $2$’s.
For each of your extra $2$’s, you can either use it on the board only once, or not use it at all.
You can not re-use the removed numbers from the board.

After replacing, you have to determine the biggest rectangle on the board which doesn’t contain any $0$.

## Input

The first line of input contains 3 numbers: $N$, $M$, $P$ where ( $1 \leq N \leq 10^5$, $1\leq M \leq 10$, $0 \leq P \leq 10$).

Each of next $N$ lines contain $M$ integers. Each integer is either $1$ or $0$.

## Output

Print $1$ number: the area of the biggest rectangle that does not contain any $0$.

## Samples

InputOutput
6 10 0
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1 1 0

9

InputOutput
6 10 2
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1 1 0

12


### Statistics

94% Solution Ratio

prodip_bsmrstuEarliest, 1M ago

BrehamPieLightest, 4.1 MB

serotoninShortest, 835B