This problem is identical to the simple coin problem (Easy) except for the constraints on $N$ and $M$.

Kuong lives in the Kingdom of Kyunghee. In the Kingdom of Kyunghee, $N$ types of coins are used, with values $P_1, P_2, \cdots, P_N$.

Interestingly, the Kingdom of Kyunghee may have coins with a value of $0$ or a negative value.

Kuong wants to pay exactly $M$ won to buy an item. Of course, even if $M$ is $0$ or negative, he must pay exactly $M$ won. Kuong has an infinite supply of each coin, so if there is a way to pay exactly $M$ won, he can always do so.

For example, if he needs to pay $94$ won using $50$ won coins and $-3$ won coins, the minimum number of coins required is $4$ (two $50$ won coins and two $-3$ won coins). It is impossible to pay exactly $94$ won with fewer coins.

Input

The first line contains the number of coin types $N$ ($0 \le N \le 2\,000$) and the amount to pay $M$ ($-10\,000 \le M \le 10\,000$), separated by a space.

The second line contains the values of each coin $P_1, P_2, \cdots, P_N$ ($-1\,000 \le P_i \le 1\,000$), separated by spaces. If $N = 0$, the second line is not provided in the input.

All input numbers are integers.

Output

Output the minimum number of coins required to pay $M$ won. If it is impossible to pay $M$ won by any means, output $-1$ instead.

Examples

Input 1

2 94
50 -3

Output 1

4

Input 2

2 999
2 4

Output 2

-1

Input 3

1 -5
-1

Output 3

5

Input 4

0 1

Output 4

-1

Input 5

2 0
1 -1

Output 5

0