Algorytmy 2
Wydawanie reszty 2
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 wiersz wyjścia zawiara minimalną liczbę monet potrzebną do wydania reszty $x$ przy użyciu monet o nominałach $c_i$. W drugim wierszy wypisz przykładowy zestaw monet dający tę resztę. 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
3 3
Wejście 2
3 10
3 6 8
Wyjście 2
-1