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