Tối thiểu số đồng xu (Minimizing Coins)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ loại đồng xu có giá trị dương, mỗi loại được dùng không giới hạn lần. Hãy tạo đúng tổng $x$ với số đồng xu ít nhất; nếu không thể thì in -1.

Input

Dòng 1 chứa $n,x$. Dòng 2 chứa $n$ giá trị phân biệt $c_1,\ldots,c_n$.

Output

In số đồng xu nhỏ nhất, hoặc -1 nếu không thể tạo $x$.

Subtask

• Subtask 1 — 20 điểm: 1 <= n <= 10; 1 <= x <= 30. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 1 <= n <= 50; 1 <= x <= 10000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= n <= 100; 1 <= x <= 1000000; 1 <= c_i <= 1000000; c_i distinct. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

3 11
1 5 7

Output

3

Giải thích

Với các đồng $1,5,7$, tổng 11 có thể tạo bởi $5+5+1$, dùng 3 đồng và đây là ít nhất.