Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Hãy xét một hệ thống tiền bao gồm ~n~ đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tạo ra một khoản tiền ~x~ bằng cách sử dụng các đồng xu có sẵn sao cho số lượng đồng xu là tối thiểu.

Ví dụ: nếu các đồng xu là ~\{1, 5, 7\}~ và tổng mong muốn là ~11~, một giải pháp tối ưu là ~5 + 5 + 1~, cần ~3~ đồng xu.

Dữ liệu vào

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~: số lượng đồng xu và tổng số tiền mong muốn.
• Dòng thứ hai có ~n~ số nguyên phân biệt ~c_1, c_2, \dots, c_n~: giá trị của mỗi đồng xu.

Kết quả

• In một số nguyên: số lượng đồng xu tối thiểu. Nếu không thể tạo ra tổng mong muốn, hãy in ~-1~.

Giới hạn

• ~1 \le n \le 100~
• ~1 \le x \le 10^6~
• ~1 \le c_i \le 10^6~

Sample Input 1

3 11
1 5 7

Sample Output 1

3

Nguồn: CSES 1634 – Minimizing Coins.