Se citesc m tipuri de bancnote, fiecare cu o valoare si o cantitate disponibila LIMITATA, si o suma S. Determinati, folosind Programarea Dinamica, in cate moduri distincte (ordinea nefiind relevanta) se poate obtine exact suma S, fara a depasi cantitatea disponibila din niciun tip de bancnota.
- Date de intrare
- Pe prima linie se citesc m si S. Urmeaza m linii, fiecare cu doua numere: valoarea si cantitatea disponibila a unui tip de bancnota.
- Date de iesire
- Se afiseaza un singur numar: numarul de moduri de a obtine suma S.
- Restrictii
- 1 <= m <= 20, 0 <= S <= 1000, 1 <= valoare <= 1000, 1 <= cantitate <= 50
Exemple
Exemplul 1
Intrare
2 6 2 3 3 2
Iesire
2
Exemplul 2
Intrare
1 5 1 3
Iesire
0