Fişierul intrare/ieşire:	lumina.in, lumina.out	Sursă	ad-hoc
Autor	Vlad Sanduleac	Adăugată de	Sanduleac Vlad •StelarCF
Timp execuţie pe test	1 sec	Limită de memorie	2048 kbytes
Scorul tău	N/A	Dificultate	3/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Lumina

Casian se strecoara intr-o baza extraterestra pentru a distruge controalele navei mama care ameninta planeta PACO. Baza este un dreptunghi de n*m patrate care au asociata o valoare li,j reprezintand nivelul de lumina. Datorita abilitatilor lui Casian, extraterestrii nu il pot vedea imediat decat daca el se afla intr-un patrat de lumina minim k sau daca suma ultimelor x casute este minim (x*k)/2. (Daca aceasta valoare este reala se ia numai partea intreaga)

Cerinta

Sa se afle lungimea minima L pe care trebuie sa o strabata Casian pentru a ajunge la controale si riscul minim r, unde riscul este suma tuturor nivelelor de lumina asociate patratelor prin care trece Casian

Date de intrare

Pe prima linie a fisierului de intrare lumina.in se afla n si m. Pe a doua linie se vor afla numerele x si k. Pe a treia linie se vor afla 4 numere reprezentand locul de unde porneste Casian si locul unde trebuie sa ajunga. Pe urmatoarele n linii se vor afla cate m numere reprezentand nivelele de lumina are patratelor.

Date de ieşire

In fisierul de iesire lumina.out se vor afisa numerele L si r, conform enuntului.

Restricţii

2 <= n, m <= 100
3 <= x <= 10
0 <= li,j <= 1000
2 <= k <= 10000
Se garanteaza ca pentru orice test exista solutie

Exemplu

Explicaţie

Casian porneste din casuta (1, 1) si poate trece prin casutele (1,2), (2,2), (3,2), (3,3), (3,4) si (4,4). Lungimea este 6. Pentru risc minim el poate trece prin (2,1) in loc de (1,2)