本题与简单硬币问题（Easy）除 $N$ 和 $M$ 的限制外，其余完全相同。

Kuong 住在庆熙王国。庆熙王国使用 $N$ 种面值的硬币，分别为 $P_1$ 元、$P_2$ 元，$\cdots$，$P_N$ 元。

奇怪的是，庆熙王国可能存在价值为 $0$ 或负数的硬币。

Kuong 想要购买商品，需要支付恰好 $M$ 元。当然，即使 $M$ 为 $0$ 或负数，也必须支付恰好 $M$ 元。Kuong 拥有无限数量的每种硬币，因此只要存在支付 $M$ 元的方法，他总能支付。

例如，如果需要用 $50$ 元硬币和 $-3$ 元硬币支付 $94$ 元，最少需要的硬币数量是 $2$ 个 $50$ 元硬币和 $2$ 个 $-3$ 元硬币，总共 $4$ 个。无法用比这更少的硬币数量支付 $94$ 元。

第一行包含硬币种类数 $N(0 \le N \le 2\,000)$ 和需要支付的金额 $M(-10\,000 \le M \le 10\,000)$，中间用空格分隔。

第二行包含每种硬币的价值 $P_1, P_2, \cdots, P_N$ $(-1\,000 \le P_i \le 1\,000)$，中间用空格分隔。如果 $N = 0$，则输入中不会给出第二行。

输入的所有数字均为整数。

输出支付 $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