To zadanie jest identyczne z prostą wersją problemu wydawania reszty (Easy), z wyjątkiem ograniczeń na $N$ oraz $M$.

Kuong mieszka w Królestwie Kyunghee. W królestwie tym używa się $N$ rodzajów monet o wartościach $P_1, P_2, \dots, P_N$.

Co ciekawe, w Królestwie Kyunghee mogą istnieć monety o wartości $0$ lub wartości ujemnej.

Kuong chce zapłacić dokładnie $M$ jednostek waluty za zakup towarów. Oczywiście, nawet jeśli $M$ wynosi $0$ lub jest liczbą ujemną, musi zapłacić dokładnie $M$. Kuong posiada nieskończoną liczbę monet każdego rodzaju, więc jeśli istnieje sposób na zapłacenie dokładnie $M$, zawsze może to zrobić.

Na przykład, jeśli musi zapłacić $94$ jednostki za pomocą monet o wartości $50$ i $-3$, minimalna liczba potrzebnych monet to $4$ (dwie monety $50$ i dwie monety $-3$). Nie da się zapłacić dokładnie $94$ przy użyciu mniejszej liczby monet.

Wejście

W pierwszej linii podano liczbę rodzajów monet $N$ ($0 \le N \le 2\,000$) oraz kwotę do zapłacenia $M$ ($-10\,000 \le M \le 10\,000$), oddzielone spacją.

W drugiej linii podano wartości poszczególnych monet $P_1, P_2, \dots, P_N$ ($-1\,000 \le P_i \le 1\,000$), oddzielone spacjami. Jeśli $N = 0$, druga linia wejścia nie występuje.

Wszystkie podane liczby są całkowite.

Wyjście

Wypisz minimalną liczbę monet potrzebną do zapłacenia kwoty $M$. Jeśli nie ma sposobu na zapłacenie dokładnie $M$, wypisz $-1$.

Przykład

Wejście 1

2 94
50 -3

Wyjście 1

4

Wejście 2

2 999
2 4

Wyjście 2

-1

Wejście 3

1 -5
-1

Wyjście 3

5

Wejście 4

0 1

Wyjście 4

-1

Wejście 5

2 0
1 -1

Wyjście 5

0