Cerința
La ferma din comuna Iepurești există un teren de forma dreptunghiulară în care fermierii satului au creat mai multe grădini în care au plantat morcovi. Terenul este împărțit în nxm
unități (n
reprezintă numărul de linii, iar m
reprezintă numărul de coloane) numite celule. Morcovii nu sunt plantați uniform astfel încât în celule diferite pot exista numere diferite de morcovi. Grădinile sunt separate între ele prin garduri de diverse forme și lățimi, gardurile ocupând și ele un număr întreg de unități din teren.
Iepurele Ronți vrea să știe în ce grădină să intre pentru a aduna cât mai mulți morcovi dintr-un singur raid asupra terenului și vă cere să-l ajutați și să-i spuneți care este numărul maxim de morcovi pe care îl adună și de unde trebuie să înceapă pentru a aduna acea cantitate. Din celula în care se află, el poate sări maxim k
unități, putând astfel să sară peste eventuale garduri dintre grădini. Ronți poate sări doar în direcțiile N
, S
, E
și V
.
Date de intrare
Fișierul de intrare ronti.in
conține pe prima linie trei numere naturale n
, m
și k
, separate printr-un spațiu, cu semnificația din enunț. Fiecare dintre următoarele n
linii conține câte m
numere naturale separate prin câte un spațiu. O valoare 0
semnifica faptul că acea unitate face parte dintr-un gard, iar o valoare nenulă reprezintă numărul de morcovi din unitate.
Date de ieșire
Fișierul de ieșire ronti.out
va conține pe prima linie doua numere naturale x
și y
, reprezentând coordonatele unității din care trebuie să pornească Ronți pentru a obține numărul maxim de morcovi, iar pe următoarea linie a fișierului numărul maxim de morcovi obținut în urma raidului.
Restricții și precizări
1 ≤ n ≤ 100
1 ≤ m ≤ 100
- Numărul de morcovi din fiecare unitate este mai mic decât
200.000
- Dacă există două drumuri cu același număr maxim de morcovi adunați, se va alege drumul care are poziția de start cea mai mică din punct de vedere lexicografic
- Perechea
(i, j)
este mai mică în sens lexicografic decât perechea(x, y)
dacăi<x
sau dacăi=x
șij<y
Exemplu 1:
ronti.in
4 8 2 1 2 0 1 1 0 0 10 3 4 0 1 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 0 3 3
ronti.out
1 1 30
Explicație
Ronți pornește din celula (1, 1)
, ia toți morcovii din grădina respectivă (10 morcovi).
Din celula (1, 2)
sare în celula (1, 4)
din grădina alăturată și ia toți morcovii (4 morcovi).
Din celula (2, 4)
sare in celula (4, 4)
din grădina alaturată și ia toți morcovii (10 morcovi).
Din celula (4, 5)
sare în celula (4, 7)
din grădina alăturată și ia toți morcovii (6 morcovi).
Cantitatea de morcovi adunată este 10 + 4 + 10 + 6 = 30
Observație. Ronți poate să înceapă și din celula (1, 8)
, insă poate lua doar 10 morcovi.
ronti.in
4 8 2 1 2 0 1 1 0 0 50 3 4 0 1 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 0 3 3
ronti.out
1 8 50
Explicație
Ronți pornește din celula (1, 8)
si ia 50 de morcovi.
Dacă Ronți pornește din celula (1, 1)
, atunci el poate lua doar 30 de morcovi.