Algorytmy 2
Wydawanie reszty
Mając dany zbiór nominałów chcemy wydać resztę przy użyciu minimalnej liczby monet. Zakładamy, że mamay nieograniczoną liczbę monet każdego nominału.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby: $n$ i $x$. Drugi wiersz zawiera $n$ liczb $c_i$.
Wyjście
Pierwszy i jedyny wiersz wyjścia zawiara minimalną liczbę monet potrzebną do wydania reszty $x$ przy użyciu monet o nominałach $c_i$. Jeśli wydanie reszty nie jest możliwe, wypisz liczbę $-1$.
Ograniczenia
- $1 \le n \le 100$
- $1 \le x \le 10^6$
- $1 \le c_i \le 10^6$
Przykłady
Wejście 1
3 6
1 3 4
Wyjście 1
2
Wejście 2
3 10
3 6 8
Wyjście 2
-1