Este problema es idéntico al problema de monedas simple (Easy), salvo por las restricciones de $N$ y $M$.

Kuong vive en el Reino de Kyunghee. En el Reino de Kyunghee se utilizan $N$ tipos de monedas con valores $P_1, P_2, \cdots, P_N$.

Curiosamente, en el Reino de Kyunghee puede haber monedas con valor $0$ o negativo.

Kuong desea pagar exactamente $M$ unidades para comprar un artículo. Por supuesto, incluso si $M$ es $0$ o negativo, debe pagar exactamente $M$ unidades. Kuong tiene una cantidad infinita de cada tipo de moneda, por lo que si existe una forma de pagar exactamente $M$ unidades, siempre podrá hacerlo.

Por ejemplo, si debe pagar $94$ unidades usando monedas de $50$ y $-3$, el número mínimo de monedas necesarias es $4$ (dos monedas de $50$ y dos monedas de $-3$). No es posible pagar exactamente $94$ unidades con un número menor de monedas.

Entrada

La primera línea contiene el número de tipos de monedas $N$ ($0 \le N \le 2\,000$) y el monto a pagar $M$ ($-10\,000 \le M \le 10\,000$), separados por un espacio.

La segunda línea contiene los valores de cada moneda $P_1, P_2, \cdots, P_N$ ($-1\,000 \le P_i \le 1\,000$), separados por espacios. Si $N = 0$, la segunda línea no se proporciona en la entrada.

Todos los números de entrada son enteros.

Salida

Imprima el número mínimo de monedas necesarias para pagar $M$ unidades. Si no es posible pagar $M$ unidades de ninguna manera, imprima $-1$ en su lugar.

Ejemplos

Entrada 1

2 94
50 -3

Salida 1

4

Entrada 2

2 999
2 4

Salida 2

-1

Entrada 3

1 -5
-1

Salida 3

5

Entrada 4

0 1

Salida 4

-1

Entrada 5

2 0
1 -1

Salida 5

0