Sledećeg meseca održaće se licitacija za kupovinu zemlje u nedavno otkrivenim naftnim poljima. Polja su rasprostranjena ispod pravougaone doline dimenzija X x Y (Y predstavlja broj redova, a X broj kolona). Donji levi hektar označen je sa (1, 1). Hektar je jedinica mere za površinu.

Tvoja kompanija ima ekskluzivno pravo da bira zemljište pre licitacije ali i ograničen budžet. Uz pomoć satelitskih snimaka koju si dobio od Tajne Komisije na zajam, a samim tim i saznanje o rasporedu naftnih polja, neće ti biti teško da izabereš parcelu koja će tvojoj kompaniji doneti najveće zalihe nafte.

• Nafne podzemne rezerve unutar istog bazena su povezane. Dva hektara su susedna ako imaju zajedničku stranu.
• Zemlju je moguće kupiti samo u pravougaonim parcelama celobrojih mera.
• Minimalna površina koja se može kupiti je 2 hektara.
• Nafta se može crpiti sa svakog hektara koji je kupljen, kopanjem bunara samo ravno nadole.
• Cena jednog hektara je 1,000,000 dinara.
• Naftna polja ispod površine se neće preklapati. (gledano odgore)

Pošto tvoja kompanija ima dugu tradiciju u eksploataciji nafte a želi da nastavi u istom trendu tvoj zadatak je da obezbediš što je moguće više nafte dostupne sa kupljene zemlje, sa budžetom koji imaš na raspolaganju. Ako postoji više rešenja koja daju istu dostupnu površinu podzemnih naftnih polja, tada biraš onu koja će biti najjeftinija. Postojaće samo jedno takvo rešenje.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom standardnog redu ulaza su dva cela broja Y i X, (0 < Y, X ≤ 50) dimenzije doline. U sledećih Y redova su X celih brojeva odvojenih praznim mestima (ID_i ≤ X x Y), sa oznakama određenog podzemnog naftnog polja. ID_i. = 0 znači da nema nafte ispod tog hektara. U sledećiem (Y + 2) redu je ceo broj M, (2,000,000 ≤ M ≤ 1,000,000,000), tvoj budžet za ovu kupovinu.

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) U prvi red standardnog izlaza ispiši 4 cela broja odvojena praznim mestima, (X_dl Y_dl X_gd Y_gd), koji predstavljaju koordinate donjeg levog i gornjeg desnog ugla parčeta doline koji ćeš kupiti sa dozvoljenim budžetom. Ako ima više rešenja sa istom količinom nafte, izaberi ono koje će ti uštedeti najviše novca. U drugi red izlaza ispiši količinu ušteđenog novca. U treći red izlaza ispiši količinu nafte u hektarima koja će tvojoj kompaniji biti na raspolaganju sa ovako kupljene zemlje.

Primer 1.

4 4
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
4012345

2 2 3 3
12345
16

Objašnjenje.

Sa 4,000,000 dinara budžeta, možeš da kupiš najviše 4 hektara doline. Najpovoljnije je da uzmeš 4 centralna hektara jer si time omogućio kompaniji da pristupi svim naftnim poljima koja su ispod doline. (to su polja sa oznakama ID = 1, 2, 3, 4). Ušteđena suma je 12,345 dinara.

Primer 2.

4 4
0 7 7 7
3 3 5 5
3 5 5 5
3 3 3 9
4012345

2 2 2 4
1012345
14

Objašnjenje.

Pravougaona površina (2,3) (3,4) omogućuje pristup do 14 hektara podzemnih rezervi doline. Do isto toliko se može dopreti kupovinom parčeta (2,2) (2,4). Medjutim pošto je veća ušteda u drugom slučaju, (2,2) (2,4) je traženo rešenje (polja sa oznakama ID = 3, 5, 7) .

{ Vanja Petrovic Tankovic i Nenad Bozidarevic - RAF, Beograd }

var Dolina           : array [0..51,0..51]   of LongInt;
    Dostupno         : array [0..2501]       of LongInt;
    Memo             : array [0..2501]       of LongInt;
    maxVrednost, minPolja, dlx, dly, gdx, gdy : LongInt;
    n, m, i, j, h, w, l                       : LongInt;
    pare, maxPolja, vrednost, iteracija       : LongInt;

Begin
  Readln(n, m);

  for i := n downto 1 do
  Begin
    for j := 1 to m do Read(Dolina[i,j]);
    Readln;
  end;
  Readln(pare);

  maxPolja := pare div 1000000;
  minPolja := 2501;

  for i := 1 to n do
    for j := 1 to m do
      if Dolina[i,j] > 0
        then inc(Dostupno[Dolina[i,j]]);

  for i := n downto 1 do
    for j := m downto 1 do
    Begin
      w := 0;
      while (j + w <= m) and (w+1 <= maxPolja) do
      Begin
        vrednost  := 0;
        h         := 0;
        Inc(iteracija);
        While (i + h <= n) and ((h+1)*(w+1) <= maxPolja) do
        Begin
    for l := 0 to w do
            if Memo[Dolina[i+h, j+l]] <> iteracija
              then Begin
                     Memo[Dolina[i+h, j+l]] := iteracija;
                     vrednost := vrednost + Dostupno[Dolina[i+h, j+l]];
                   end;
          if (vrednost > maxVrednost) or
             (vrednost = maxVrednost) and ((h+1)*(w+1) < minPolja)
            then Begin
                   minPolja   := (h+1)*(w+1);
                   maxVrednost:= vrednost;
                   dlx        := j;
                   dly        := i;
                   gdx        := j+w;
                   gdy        := i+h;
     end;
          inc(h);
        end;
        inc(w);
      end;
    end;
  Writeln(dlx, ' ', dly, ' ', gdx, ' ',gdy);
  Writeln(pare - minPolja * 1000000);
  Writeln(maxVrednost);
end.