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

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile 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 ≤ l_i,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)