Problem description

Nadszedł czas, by powiedzieć sobie jasno o czym jest zadanie, bez żadnych historyjek i tym podobnych “bajerów”.

Dany jest zbiór monet o określonych nominałach. Chcemy wydać zadaną kwotę K za pomocą najmniejszej liczby nominałów. Należy wyznaczyć optymalny sposób wydania reszty (za pomocą najmniejszej liczby nominałów). Każdej monety wolno użyć co najwyżej raz.

Napisz program, który: wczyta liczbę nominałów oraz te nominały, wyznaczy minimalną liczbę monet, niezbędnych do wydania kwoty K, wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i K, oddzielone pojedynczym odstępem i określające kolejno: liczbę nominałów oraz kwotę do wydania. W drugim (i ostatnim) wierszu wejścia znajduje się ciąg N dodatnich liczb całkowitych A_i, pooddzielanych pojedynczymi odstępami. Są to nominały monet, których można użyć do wydania kwoty K.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalna liczba nominałów niezbędna do wydania kwoty K.

Jeśli wydanie kwoty jest niemożliwe zamiast tego należy wypisać NIE.

Ograniczenia

1 ≤ N ≤ 40, 0 ≤ K ≤ 10¹⁸, 0 ≤ A_i ≤ 10¹⁷.

W testach wartych łącznie 15% maksymalnej punktacji: K ≤ 50 000.

W testach wartych łącznie 50% maksymalnej punktacji: N ≤ 20.

Przykład

4 8
4 5 1 2

3

5 16
1 2 3 4 5

NIE