Se citesc m tipuri de monede (valori date, disponibile in cantitate nelimitata) si o suma S. Determinati, folosind Programarea Dinamica, in cate secvente ORDONATE distincte de monede se poate obtine suma S (doua secvente care folosesc aceleasi monede, dar intr-o alta ordine, sunt considerate distincte).
- 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 de secvente ordonate ce formeaza suma S.
- Restrictii
- 1 <= m <= 100, 0 <= S <= 10000, 1 <= valoare moneda <= 10000
Exemple
Exemplul 1
Intrare
3 4 1 2 3
Iesire
7
Exemplul 2
Intrare
2 5 1 2
Iesire
8