| Submit | All submissions | Best solutions | Back to list |
HELPPM - Help the PM! |
| English | Vietnamese |
|
In 2050, Le Don Khue has become the Prime Minister of Vietnam. He has to consider a logging plan of K m3 wood in a forest for export. The forest is a MxN km2 rectangular area. For easy management, the forest is divided into MxN cells (M rows and N columns). The rows are numbered as 1 to M from top to bottom. The columns are numbered as 1 to N from left to right. The cell at row i and column j has coordinates (i, j). The quantity of wood (m3) in each cell is already known. The PM decided to give permission for logging. The logging area should also be rectangular. The PM wants to find an area as small as possible but there is still enough wood in this area for export. Has not been programming for a long time, the PM needs your help. Let's help him! |
|
Input
- The first line contains three integers M, N, K (1 ≤ M, N ≤ 500, 1 ≤ K ≤ 109).
- The ith line in the next M lines contains N non-negative integers in which the jth number is the quantity of wood in cell (i, j). The quantity of wood in each cell is not larger than 104 m3.
Output
If there is no logging area that give enough wood for export, print -1. Otherwise, print two lines:
- The first line contains the minimum possible area of the logging area.
- The second line contains four integers that are coordinates of the top left and bottom right corner of the logging area. If there is more than one possible area, print the coordinates of any of them.
Example
Input 3 3 19 5 4 0 4 7 0 0 0 2 Output 4 1 1 2 2
| Added by: | Lê Đôn Khuê |
| Date: | 2008-07-18 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
| Resource: | VNOI Marathon '08 - Round 6/DivB Problem Setter: Lê Đôn Khuê |
