この問題は、簡単なコイン問題 (Easy) と $N$ および $M$ の制約を除いて同一の問題です。

クオンはキョンヒ王国に住んでいる。キョンヒ王国では、$P_1$ 円、$P_2$ 円、$\cdots$、$P_N$ 円の $N$ 種類のコインを使用する。

不思議なことに、キョンヒ王国には $0$ または負の価値を持つコインが存在する場合がある。

クオンは買い物をし、正確に $M$ 円を支払おうとしている。もちろん、$M$ が $0$ または負の場合でも、正確に $M$ 円を支払わなければならない。クオンは各コインを無限に持っているため、正確に $M$ 円を支払う方法が存在すれば、常に支払うことができる。

例えば、$50$ 円コインと $-3$ 円コインで $94$ 円を支払う必要がある場合、必要なコインの最小枚数は $50$ 円 $2$ 枚、$50$ 円 $2$ 枚と $-3$ 円 $2$ 枚の計 $4$ 枚である。これより少ない枚数で正確に $94$ 円を支払うことはできない。

入力

1行目にコインの種類数 $N (0 \le N \le 2\,000)$ と支払う金額 $M (-10\,000 \le M \le 10\,000)$ が空白区切りで与えられる。

2行目に各コインの価値 $P_1, P_2, \cdots, P_N (-1\,000 \le P_i \le 1\,000)$ が空白区切りで与えられる。もし $N = 0$ ならば、入力に2行目は与えられない。

入力されるすべての数は整数である。

出力

$M$ 円を支払うために必要なコインの最小枚数を出力せよ。どのような方法でも $M$ 円を支払うことができない場合は、代わりに $-1$ を出力せよ。

入出力例

入力 1

2 94
50 -3

出力 1

4

入力 2

2 999
2 4

出力 2

-1

入力 3

1 -5
-1

出力 3

5

入力 4

0 1

出力 4

-1

入力 5

2 0
1 -1

出力 5

0