== include(page="template/taskheader" task_id="piete") ==
Poveste şi cerinţă...
Î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.
h2. Date de intrare
Fişierul de intrare $piete.in$ ...
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**.
h2. Date de ieşire
În fişierul de ieşire $piete.out$ ...
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$.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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.
table(example). |_. piete.in |_. piete.out |
| 2 3 3 6
4 7 8
6 5
| -1
|
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") ==