Matei are m sticle, initial goale, cu volumele date. El poate efectua urmatoarele operatii:
- ia o sticla si o umple complet de la robinet;
- ia doua sticle si varsa cat de mult poate din prima in a doua, fie pana cand prima sticla se goleste, fie pana cand a doua sticla se umple.
Matei vrea sa obtina o sticla care sa contina exact T litri de apa. Care este numarul minim de operatii necesare pentru a obtine acest lucru? Daca acest lucru nu este posibil, se afiseaza -1.
- Date de intrare
- Pe prima linie se citeste numarul intreg m, numarul de sticle. Pe a doua linie se citesc m numere intregi, capacitatile sticlelor. Pe a treia linie se citeste numarul intreg T, cantitatea dorita.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul minim de operatii necesare pentru ca o sticla sa contina exact T litri, sau -1 daca acest lucru nu este posibil.
- Restrictii
- 2 <= m <= 4 1 <= capacitate <= 12 0 <= T <= capacitatea maxima dintre sticle
Exemple
Exemplul 1
Intrare
4 2 8 10 20 1
Iesire
-1
Exemplul 2
Intrare
2 3 5 1
Iesire
4