Cho một tập hợp các mệnh giá tiền xu và một tổng tiền . Nhiệm vụ của bạn là tìm số lượng xu tối thiểu cần thiết để tạo ra tổng . Bạn có thể sử dụng mỗi mệnh giá tiền xu không giới hạn số lần.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và : số lượng mệnh giá và tổng tiền mục tiêu.
Dòng thứ hai chứa số nguyên : các mệnh giá tiền xu.
Kết quả: In ra số lượng xu tối thiểu. Nếu không thể tạo ra tổng , in ra -1.
Ví dụ:
Dữ liệu:
3 11
1 5 7
Kết quả:
3
Giải thích: Ta có thể tạo tổng 11 bằng cách dùng hai đồng 5 và một đồng 1 ().
