There is a rectangular puzzle board containing number of places. Each place contains a number: either or .
You are given P number of extra ’s. You can replace any of the numbers on the board with your extra ’s.
For each of your extra ’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 .
The first line of input contains 3 numbers: , , where ( , , ).
Each of next lines contain integers. Each integer is either or .
Print number: the area of the biggest rectangle that does not contain any .
Input | Output |
---|---|
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 |
Input | Output |
---|---|
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 |