Một điểm rút tiền ATM có các mệnh giá lần lượt 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng.

Viết chương trình nhập vào số tiền M (0 < M < 10⁹ ) đồng. Hãy tìm cách đổi số tiền M thành ít tờ tiền nhất. Biết rằng số tiền giới hạn mỗi lần rút tiền ATM có giá trị thấp nhất là 50.000 đồng và mỗi loại tờ tiền không quá 1000 tờ.

Dữ liệu vào: Gồm duy nhất số M

Dữ liệu ra: Bao gồm :

+ Dòng 1: ghi số tờ tiền ít nhất phải trả

+ Dòng 2: Ghi các số ứng với số tờ cần trả cho mỗi loại tiền theo thứ tự : 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng. Nếu không đổi được thì ghi ra file ‘KHONG THUC HIEN DUOC’.

Ví dụ: