Bài toán này giống hệt với bài toán đổi tiền đơn giản (Easy) ngoại trừ các giới hạn của $N$ và $M$.

Kuong sống ở Vương quốc Kyunghee. Tại Vương quốc Kyunghee, người ta sử dụng $N$ loại tiền xu với mệnh giá lần lượt là $P_1, P_2, \cdots, P_N$.

Điều kỳ lạ là ở Vương quốc Kyunghee, có thể tồn tại những đồng xu có giá trị bằng $0$ hoặc âm.

Kuong muốn trả chính xác $M$ đồng để mua một món hàng. Tất nhiên, ngay cả khi $M$ là $0$ hoặc số âm, anh ấy vẫn phải trả chính xác $M$ đồng. Vì Kuong có vô số lượng tiền xu cho mỗi loại, nếu có cách để trả chính xác $M$ đồng, anh ấy luôn có thể thực hiện được.

Ví dụ, nếu bạn cần trả $94$ đồng bằng các đồng xu $50$ đồng và $-3$ đồng, số lượng tiền xu tối thiểu cần dùng là $4$ đồng (hai đồng $50$ và hai đồng $-3$). Không thể trả chính xác $94$ đồng với số lượng tiền xu ít hơn thế.

Dữ liệu vào

Dòng đầu tiên chứa số loại tiền xu $N$ ($0 \le N \le 2\,000$) và số tiền cần trả $M$ ($-10\,000 \le M \le 10\,000$), cách nhau bởi dấu cách.

Dòng thứ hai chứa giá trị của mỗi đồng xu $P_1, P_2, \cdots, P_N$ ($-1\,000 \le P_i \le 1\,000$), cách nhau bởi dấu cách. Nếu $N = 0$, dòng thứ hai sẽ không xuất hiện trong dữ liệu vào.

Tất cả các số được nhập vào đều là số nguyên.

Dữ liệu ra

In ra số lượng tiền xu tối thiểu cần thiết để trả $M$ đồng. Nếu không có cách nào để trả chính xác $M$ đồng, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 1

2 94
50 -3

Dữ liệu ra 1

4

Dữ liệu vào 2

2 999
2 4

Dữ liệu ra 2

-1

Dữ liệu vào 3

1 -5
-1

Dữ liệu ra 3

5

Dữ liệu vào 4

0 1

Dữ liệu ra 4

-1

Dữ liệu vào 5

2 0
1 -1

Dữ liệu ra 5

0