Ce problème est identique au problème des pièces (facile), à l'exception des contraintes sur $N$ et $M$.

Kuong vit dans le royaume de Kyunghee. Dans ce royaume, on utilise $N$ types de pièces de valeurs $P_1, P_2, \cdots, P_N$.

Il est intéressant de noter que dans le royaume de Kyunghee, il peut exister des pièces ayant une valeur de $0$ ou une valeur négative.

Kuong souhaite payer exactement $M$ pour acheter un article. Bien entendu, même si $M$ est égal à $0$ ou est un nombre négatif, il doit payer exactement $M$. Kuong possède une quantité infinie de chaque type de pièce, donc s'il existe un moyen de payer exactement $M$, il peut toujours le faire.

Par exemple, si vous devez payer $94$ avec des pièces de $50$ et $-3$, le nombre minimum de pièces nécessaires est de $4$ (deux pièces de $50$ et deux pièces de $-3$). Il est impossible de payer exactement $94$ avec un nombre de pièces inférieur.

Entrée

La première ligne contient le nombre de types de pièces $N$ ($0 \le N \le 2\,000$) et le montant à payer $M$ ($-10\,000 \le M \le 10\,000$), séparés par un espace.

La deuxième ligne contient les valeurs de chaque pièce $P_1, P_2, \cdots, P_N$ ($-1\,000 \le P_i \le 1\,000$), séparées par un espace. Si $N = 0$, la deuxième ligne n'est pas fournie dans l'entrée.

Tous les nombres fournis en entrée sont des entiers.

Sortie

Affichez le nombre minimum de pièces nécessaires pour payer $M$. S'il est impossible de payer $M$ par quelque méthode que ce soit, affichez $-1$ à la place.

Exemples

Entrée 1

2 94
50 -3

Sortie 1

4

Entrée 2

2 999
2 4

Sortie 2

-1

Entrée 3

1 -5
-1

Sortie 3

5

Entrée 4

0 1

Sortie 4

-1

Entrée 5

2 0
1 -1

Sortie 5

0