To zadanie jest identyczne z zadaniem "Prosty problem z monetami (Hard)", 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, \cdots, 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$ za zakupiony towar. 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$ 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$) oraz kwotę do zapłaty $M$ ($-1\,000 \le M \le 1\,000$), oddzielone spacją.

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

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