Se citesc m tipuri de monede (valori date, disponibile in cantitate nelimitata) si o suma S. Determinati, folosind Programarea Dinamica, numarul minim de monede necesare pentru a obtine exact suma S, indiferent daca sistemul de monede este canonic sau nu. Daca suma S nu poate fi obtinuta, afisati -1.
- Date de intrare
- Pe prima linie se citesc m si S. Pe a doua linie se citesc cele m valori ale monedelor.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de monede necesare, sau -1 daca suma S nu poate fi obtinuta.
- Restrictii
- 1 <= m <= 100, 1 <= S <= 100000, 1 <= valoare moneda <= 100000
Exemple
Exemplul 1
Intrare
3 11 1 2 5
Iesire
3
Exemplul 2
Intrare
2 3 2 4
Iesire
-1