Rectangular
Land
Two good friends decided to buy some land in some area of
the city they live in. The city is described as a square matrix with side N, and each unit square has a land
value attached - an integer in the range -150..150.
The first
friend wants to buy a rectangular land having P rows (of the city matrix) and Q columns, completely enclosed inside the city matrix. Besides
that, he would like his land to have the maximum value possible. The value of
the land is equal to the sum of the values of the unit squares enclosed by it.
The second friend wants to buy some land, too. He would
like his land to have a ractangular shape, Q columns and AT MOST P rows (this means it may have 1 or 2 or
.. or P rows) and, of course, to
have the maximum value
possible. The value of the land is defined as in the case of the first friend.
Input
Data
The first line of the input file RLAND.IN will contain
the integers N,P and Q, separated by blanks.The next N
lines will contain N integers, representing the land value of the corresponding
unit square. They will be separated by blanks.
Output
Data
The first line of output file RLAND.OUT will contain
the numbers S i j, separated by blanks, representing the maximum value of the
land the first friend wants to buy, the row and the column of the top left corner
of this land. If there are more solutions, then you may print any of them.
The second line will contain the integers X R a b,
separated by blanks, meaning: the maximum value of the land the second friend
wants to buy, the number of rows of this land (1<=R<=P), the row and the column
of the top-left corner of the land. If there are more solutions, you may print
any of them.
Limits
·
4 <= N <= 150
·
1 <= P,Q <= N
·
The score for every test case wil be distributed
as follows:
- 60% , if the
maximum value and a correct rectangle for the first type of land is found
- 40% , if the
maximum value and a correct rectangle for the second type of land is found
Example
RLAND.IN RLAND.OUT
4 2 3 1
2 2
-1 -1 -1 -1 2
1 3 2
-1
1 -1 -1
-1 -1 -1 4
-1 -1 -1 -1
Time limit: 0.25
seconds/test case