== include(page="template/taskheader" task_id="piete") ==

Într-o ţară există **N** oraşe, fiecare oraş având o piaţă unde oamenii pot vinde şi cumpăra articole. Sunt **M** tipuri de articole care se comercializează şi fiecare piaţă are propriul ei preţ de vânzare şi cumpărare pentru oricare dintre cele **M** articole, nu neapărat diferit de cel din alte pieţe. Fiind fată deşteaptă, Claudia şi-a dat seama că poate să facă profit cumpărând articole dintr-un oraş şi vânzându-le în alt oraş. Ea îşi propune să-şi sporească economiile achiziţionând şi vânzând produse în pieţele din ţară şi să ajungă la o sumă finală pe care poate să o şi depăşească.
Datorită  sistemului strict impus de către regele tiran, comerţul în ţară este descurajat. Regele a impus ca nimeni să nu poată călători dintr-un oraş în altul având mai multe articole de acelaşi tip şi îi obligă pe toţi comercianţii ce intră într-un oraş să îşi vândă toate articolele aduse, înainte de a face alte achiziţii. De asemenea, la orice transport de articole dintr-un oraş în altul,  comerciantul respectiv va primi o bulină neagră în condica regelui.
 
h2. Cerinţă
 
Scrieţi un program care să o ajute pe Claudia să ajungă cel puţin la suma finală dorită, cu un număr minim de buline negre înregistrate în condica regelui.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie a fişierului **piete.in** se află patru numere naturale nenule **N**, **M**, **S**, **F** separate prin câte un spaţiu, cu semnificaţia: **N** – numărul de oraşe; **M** – numărul de tipuri de articole din fiecare piaţă; **S** – o sumă de bani ce reprezintă economiile iniţiale ale Claudiei; **F** - o sumă de bani  ce reprezintă suma finală dorită. Pe următoarele **N** linii se află câte **M** numere separate prin câte un spaţiu: al **j**-lea număr de pe linia **i** reprezintă preţul de vânzare/cumpărare a articolului **j** în piaţa **i**.

Fişierul de intrare $piete.in$ ...

h2. Date de ieşire

Pe prima linie a fişierului **piete.out** se găseşte numărul minim de buline negre pe care le va primi Claudia, dacă reuşeşte să ajungă cel puţin la suma **F**. Dacă ea nu are nicio modalitate să ajungă la suma **F** atunci se va afişa $-1$.

În fişierul de ieşire $piete.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 10$
* $1 ≤ M ≤ 10$
* $1 &le S &le F &le 100$
* $0 ≤ p[i, j] ≤ 100$ $p[i, j] =$ preţul articolului **j** la piaţa **i**
* există drum direct între oricare două oraşe
* în orice piaţă, preţul de vânzare al unui articol este acelaşi cu preţul de cumpărare al acestuia
h2. Exemplu

* $... ≤ ... ≤ ...$

table(example). |_. piete.in |_. piete.out |
| 3 4 10 20
5 1 16 4
4 2 13 3
6 3 20
| 2
|
 
h3. Explicaţie
 
Cumpără articolele 1, 2 şi 4 din oraşul 1 (rămâne cu 0 bani). Merge în oraşul 3 şi le vinde. Are acum 14 bani şi o bulină neagră. Cumpără articolul 3 din oraşul 2 (1 ban rămas). Merge în oraşul 3 şi îl vinde. Are acum 21 bani şi 2 buline. A obţinut suma dorită şi numărul de buline negre este minim.

h2. Exemplu

table(example). |_. piete.in |_. piete.out |

| 2 3 3 6
4 7 8
6 5
| -1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Nu poate cumpăra niciun articol deci nu are cum să facă profit

...

== include(page="template/taskfooter" task_id="piete") ==

== include(page="template/taskfooter" task_id="piete") ==