Este problema es idéntico al problema de monedas simple (Hard), excepto 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 de $P_1, P_2, \dots, P_N$.

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

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

Por ejemplo, si debe pagar $94$ utilizando 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$ con menos monedas que esa.

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

La segunda línea contiene los valores de cada moneda $P_1, P_2, \dots, 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.

Imprima el número mínimo de monedas necesarias para pagar $M$. Si no hay forma de pagar $M$, 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