本題除了 $N$ 與 $M$ 的限制外，與簡單硬幣問題 (Easy) 相同。

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