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