Rút tiền ATM Biết trong máy ATM có những loại tiền với mệnh giá L1, L2,…, LK với số lượng tương ứng là S1, S2,…, SK tờ mỗi loại. Khách hàng cầ

Rút tiền ATM
Biết trong máy ATM có những loại tiền với mệnh giá L1, L2,…, LK với số lượng tương ứng là S1, S2,…, SK tờ mỗi loại.
Khách hàng cần rút số tiền ST tại máy ATM (giả sử số tiền cần rút ST luôn nhỏ hơn số dư trong tài khoản của khách hàng).
Yêu cầu:Bạn hãy lập trình cho biết có bao nhiêu phương án máy ATM có thể đưa ra số tiền tương ứng với nhu cầu rút tiền của khách hàng, đồng thời đưa ra cách trả tiền tối ưu với số tờ tiền nhận được là ít nhất.
Dữ liệu vào: Đọc dữ liệu tiền từ tệp văn bản BAI4.INP gồm:
– Dòng thứ nhất: Ghi 2 số nguyên dương ST và SL thể hiện số tiền cần rút và số loại tiền có trong máy. Mỗi số phân biệt bởi một dấu cách (10<= ST <= 3000; 1 <= SL<=6). - SL dòng tiếp theo lần lượt ghi mệnh giá tiền Li và số lượng tiền Si tương ứng. Mỗi số phân biệt bởi một dấu cách (10<=Li<=500; 0<=Si<=100) Dữ liệu ra: Ghi kết quả vào tệp văn bản BAI4.OUT * Nếu không có cách đưa ra số tiền cần rút: - Ghi vào tệp số: 0 * Nếu có cách đưa ra số tiền cần rút: - Dòng đầu tiên ghi 2 số nguyên dương SC và TT (SC: số cách đưa ra số tiền cần rút, TT: số lượng tờ tiền rút được tối ưu (ít nhất)) - Các dòng tiếp theo ghi thông tin cách trả tiền của 1 cách tối ưu. Cụ thể: mỗi dòng ghi 2 số nguyên dương Li và Ki, phân biệt với nhau bởi dấu cách. (Với Li: mệnh giá loại tiền thứ i của cách trả tối ưu, Ki số lượng tờ tiền cần trả tương ứng với mệnh giá tiền Li của cách trả tối ưu), sao cho: L1*K1+L2*K2+ …+Lm*Km = ST K1+K2+…+Km = TT Ví dụ 1: BAI4.INP BAI4.OUT 2019 4 1 5 2 5 5 1 10 0 0 Ví dụ 2: BAI4.INP BAI4.OUT 19 4 1 5 2 5 5 1 10 0 1 10 1 4 2 5 5 1