Mô tả bài toán

Bài toán: Cho một số tiền cần trả ~amount~ và một danh sách các mệnh giá tiền ~coins~. Tìm cách dổi số tiền ~amount~ bằng ít tờ tiền nhất có thể, sử dụng các mệnh giá đã cho.

Input:

Số tiền cần trả ~amount~ (số nguyên dương)

Danh sách các mệnh giá tiền ~coins~ (mảng số nguyên dương)

Output:

Danh sách các mệnh giá tiền cần sử dụng ít nhất (theo thứ tự ưu tiên mệnh giá lớn trước)

Tổng số tờ tiền sử dụng

Ví dụ:

Input:

67
1 5 10 25

Output:

25 25 10 5 1 1 
6

Giải thích: 25 + 25 + 10 + 5 + 1 + 1 = 67