Limits 1s, 512 MB

There is a rectangular puzzle board containing N×MN \times Mnumber of places. Each place contains a number: either 11 or 00.

You are given P number of extra 22 ’s. You can replace any of the numbers on the board with your extra 22 ’s.
For each of your extra 22 ’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 00.

Input

The first line of input contains 3 numbers: NN, MM, PP where ( 1N1051 \leq N \leq 10^5, 1M101\leq M \leq 10, 0P100 \leq P \leq 10).

Each of next NN lines contain MM integers. Each integer is either 11 or 00.

Output

Print 11 number: the area of the biggest rectangle that does not contain any 00.

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

Submit

Login to submit.

Statistics

95% Solution Ratio
prodip_bsmrstuEarliest, Nov '21
s_semicolonFastest, 0.0s
BrehamPieLightest, 4.1 MB
serotoninShortest, 835B
Toph uses cookies. By continuing you agree to our Cookie Policy.