本題除了 $N$ 與 $M$ 的限制外，與「簡單硬幣問題 (Hard)」完全相同。

Kuong 住在慶熙王國。慶熙王國使用 $N$ 種面額的硬幣，分別為 $P_1, P_2, \dots, P_N$ 元。

特別的是，慶熙王國可能存在價值為 $0$ 或負數的硬幣。

Kuong 想要購買商品，並支付剛好 $M$ 元。當然，即使 $M$ 為 $0$ 或負數，也必須支付剛好 $M$ 元。由於 Kuong 擁有無限數量的每一種硬幣，只要存在支付剛好 $M$ 元的方法，他一定能支付。

例如，若要用 $50$ 元硬幣與 $-3$ 元硬幣支付 $94$ 元，最少需要 $50$ 元硬幣 $2$ 個與 $-3$ 元硬幣 $2$ 個，總共 $4$ 個硬幣。無法用比這更少的硬幣數量支付剛好 $94$ 元。

輸入格式

第一行包含硬幣種類數 $N(0 \le N \le 2)$ 與目標金額 $M(-1\,000 \le M \le 1\,000)$，兩者以空白分隔。

第二行包含各硬幣的面額 $P_1, P_2, \dots, 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