Fişierul intrare/ieşire:	zidar.in, zidar.out	Sursă	ONI 2007, clasa 10
Autor	Adrian Vladu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Zidar

Nu se stie de ce, ai decis subit sa incepi o cariera in constructii. Zidurile pe care le construiesti sunt formate din caramizi cubice de latura 1, asezate in mai multe straturi.
Pentru a proiecta un astfel de zid, ai trasat un caroiaj format din MxN patrate de latura 1, organizate in M linii si N coloane. Liniile caroiajului sunt numerotate de la 1 la M, incepand de jos in sus, iar coloanele sunt numerotate de la 1 la N de la stanga la dreapta.

Fiecare casuta a caroiajului are asociat un anumit cost, care trebuie platit in cazul in care plasam o caramida in casuta respectiva. Costul construirii unui zid este egal cu suma costurilor casutelor in care sunt plasate caramizile zidului.
Zidurile tale trebuie sa respecte urmatoarele conditii:

1. fiecare strat de caramizi este format dintr-o singura secventa de caramizi, oricare doua caramizi consecutive fiind adiacente (mai exact, caramizile de pe un strat sunt plasate in casute ale caroiajului situate pe aceeasi linie, pe coloane consecutive);
2. cel putin o caramida de pe fiecare strat i trebuie sa fie asezata pe o alta caramida de pe stratul de dedesubt (i-1); cel mai de jos strat trebuie sa fie asezat pe pamant (pamantul fiind sub linia 1 a caroiajului);
3. numarul de caramizi folosit in constructia zidului nu trebuie sa depaseasca un numar natural X.

Cerinta

Fiind un zidar dornic de afirmare si stiind ca dispui de o suma de T euro, calculeaza numarul maxim de caramizi pe care le poti folosi in constructia unui zid care costa cel mult T euro.

Date de intrare

Fisierul de intrare zidar.in contine pe prima linie patru numere naturale M N X T separate prin cate un spatiu cu semnificatia din enunt. Pe fiecare dintre urmatoarele M linii se afla cate N numere naturale cuprinse intre 1 si 100 reprezentand costul asezarii unei caramizi pentru fiecare dintre casutele caroiajului (mai precis, elementul j de pe a (i+1)-a linie a fisierului de intrare reprezinta costul asezarii unei caramizi in casuta de pe linia i si coloana j a caroiajului).

Date de iesire

Fisierul de iesire zidar.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul maxim de caramizi pe care il poate contine zidul tau, respectand conditiile impuse.

Restrictii

• 1 ≤ M ≤ 50
• 1 ≤ N ≤ 20
• 1 ≤ X ≤ 60
• 1 ≤ T ≤ 10000
• Pentru 30% din teste T ≤ 60. Pentru 60% din teste N ≤ 10.

Exemplu

Explicatie

Pentru a construi zidul marcat in figura ai nevoie de exact 8 euro. Nu se pot construi ziduri cu mai multe caramizi folosind aceasta suma de bani.

Cum se trimit solutii?