Fişierul intrare/ieşire:	piete.in, piete.out	Sursă	Concursul National Urmasii lui Moisil 2012, clasele 11-12
Autor	Alexandru Paicu	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

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.

Restricţii

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ 10
• 1 ≤ S ≤ F ≤ 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

Exemplu

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.

Explicaţie

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

Cum se trimit solutii?