zidar

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 $M \cdot N$ 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$.

Figura 1 din enunțul original al problemei zidar.Mărește schema ↗

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 și precizări

• $1 \leq M \leq 50$;
• $1 \leq N \leq 20$;
• $1 \leq X \leq 60$;
• $1 \leq T \leq 10 \ 000$;
• Pentru $30\%$ din teste $T \leq 60$. Pentru $60\%$ din teste $N \leq 10$.

Exemplu

zidar.in

4 5 20 8
2 2 3 2 1
4 7 1 2 3
2 1 1 1 1
1 2 5 7 3

zidar.out

6

Explicație

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.

Figura 2 din enunțul original al problemei zidar.Mărește schema ↗