Một điểm rút tiền ATM có các lại tiền giá lần lượt như sau: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng (mỗi loại có 1000 tờ). Một khách hàng cần rút ra một số tiền M đồng (Giả sử rằng sau khi đã kiểm tra đầy đủ các thông số về bảo mật cá nhân). Biết rằng số tiền giới hạn mỗi lần rút tại điểm rút tiền ATM có giá trị thấp nhất là 50.000 đồng. Hãy tìm cách trả sao cho khách hàng nhận được số lượng tờ tiền là ít nhất.

Viết chương trình giải quyết các yêu cầu trên.

Input (Dữ liệu vào) nhập từ bàn phím gồm một số nguyên dương là số tiền cần rút, không quá 1 tỉ đồng.

Ghi ra màn hình:

• Nếu không có cách trả ghi 1 dòng duy nhất có nội dung: KHONG THUC HIEN DUOC.

• Nếu có cách trả thì:

• Dòng 1: ghi số lượng 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.