Nu se ştie de ce, ai decis subit să începi o carieră în construcţii. Zidurile pe care le construieşti sunt formate din cărămizi cubice de latură 1, aşezate în mai multe straturi.
Pentru a proiecta un astfel de zid, ai trasat un caroiaj format din MxN pătrate de latură 1, organizate în M linii şi N coloane. Liniile caroiajului sunt numerotate de la 1 la M, începând de jos în sus, iar coloanele sunt numerotate de la 1 la N de la stânga la dreapta.
Fiecare căsuţă a caroiajului are asociat un anumit cost, care trebuie plătit în cazul în care plasăm o cărămidă în căsuţa respectivă. Costul construirii unui zid este egal cu suma costurilor căsuţelor în care sunt plasate cărămizile zidului.
Zidurile tale trebuie să respecte următoarele condiţii:
1. fiecare strat de cărămizi este format dintr-o singură secvenţă de cărămizi, oricare două cărămizi consecutive fiind adiacente (mai exact, cărămizile de pe un strat sunt plasate în căsuţe ale caroiajului situate pe aceeaşi linie, pe coloane consecutive);
2. cel puţin o cărămidă de pe fiecare strat i trebuie să fie aşezată pe o altă cărămidă de pe stratul de dedesubt
(i-1); cel mai de jos strat trebuie să fie aşezat pe pământ (pământul fiind sub linia 1 a caroiajului);
3. numărul de cărămizi folosit în construcţia zidului nu trebuie să depăşească un număr natural X.
Cerinţă
Fiind un zidar dornic de afirmare şi ştiind că dispui de o sumă de T euro, calculează numărul maxim de cărămizi pe care le poţi folosi în construcţia unui zid care costă cel mult T euro.
Date de intrare
Fişierul de intrare zidar.in conţine pe prima linie patru numere naturale M N X T separate prin câte un spaţiu cu semnificaţia din enunţ. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi 100 reprezentând costul aşezării unei cărămizi pentru fiecare dintre căsuţele caroiajului (mai precis, elementul j de pe a (i+1)-a linie a fişierului de intrare reprezintă costul aşezării unei cărămizi în căsuţa de pe linia i şi coloana j a caroiajului).
Date de ieşire
Fişierul de ieşire zidar.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul maxim de cărămizi pe care îl poate conţine zidul tău, respectând condiţiile impuse.
Restricţii
1 ≤ M ≤ 50
1 ≤ N ≤ 20
1 ≤ X ≤ 60
1 ≤ T ≤ 10000
Pentru 30% din teste T ≤ 60. Pentru 60% din teste N ≤ 10.
Exemple
zidar.in
zidar.out
Explicaţii
4 5 20 8
2 2 3 2 1
4 7 1 2 3
2 1 1 1 1
1 2 5 7 3
6
Pentru a construi zidul marcat în figură ai nevoie de exact 8 euro. Nu se pot construi ziduri cu mai multe cărămizi folosind această sumă de bani.
