Codah ClubУпражнявай. Изпращай. Напредвай.
Вход
Български
#0004B7

O-Oil Fields

Next month will be auction for buying land on recently discovered new oil fields. Fields are spread under rectangular valley X by Y (Y represented number of rows and X represented number of columns). Lower left hectare have coordinate (1, 1). Hectare is square unit of land surface.


Your company have limited budget but also have right to choose and buy land before auction start. What sellers don’t know is that you have some satellite image of oil field positions


    • No disjoint area of same oil field below surface. Two hectare units are joint if both have same side.
    • Land on surface will be sell only in rectangular parts with integer sides.
    • Minimal area to buy is two hectares.
    • You can pump out oil from every oil field reachable from your land by digging straight downward.
    • Price of one hectare is $1,000,000.
    • No two oil fields share same part of land (looking from above).

Since your company had long tradition in oil producing, equipment supply is unlimited. Your only goal is to take as much oil reserve as possible with your budget. If exist more then one part of land with maximal amount of reachable oil, you will take one that spare more money to your company. It will be only one part of valley match this conditions.


Image: oilfields

InputIn first row of standard input are two integers Y and X, (0 < Y,X <= 50) dimension of valley.
Next Y rows of standard input contain X integers separated by blank space (IDi <= X x Y), identify oil field covered with this particular hectare of land. IDi = 0 means that no oil below this hectare.
In next row (Y+2) of standard input is integer M, (2,000,000 <= M <= $1,000,000,000), budget for this purchase.

OutputIn first row of standard output write 4 integers separated with blank space (Xll Yll Xur Yur), coordinate of lower left and upper right rectangular part of valley, you can buy with proposed budget. If there is more than one solution, choose one that maximize remained money.
In second row of standard output write what is remained amount of money.
In third row of standard output write area of oil fields in hectares, available to you from your new land.

Input:
4 4
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
4012345
Output:
2 2 3 3
12345
16

Ulaz:
4 4
0 1 1 1
2 2 3 3
2 3 3 3
2 2 2 4
4012345
Izlaz:
2 2 2 4
1012345
14

Input:
4 4
0 7 7 7
3 3 5 5
3 5 5 5
3 3 3 9
4012345
Output:
2 2 2 4
1012345
14

Explanation for example 1: with $4,000,000 for purchase, you can buy at most 4 hectare of land. Best solution is to buy 4 hectares in middle of valley because you can reach all 16 hectares of oil reserve in valley (oil fields with ID = 1, 2, 3, 4). In that case you spare $12,345.

Explanation for example 3: with rectangular area (2,3) (3,4) you can reach 14 hectares of oil reserve as well as you buy (2,2) (2,4) but since you spare more money in second case, (2,2) (2,4) is desired solution (oil fields with ID = 3, 5, 7) .

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.