Đề bài

Một máy ATM có sẵn các loại tiền mệnh giá: 1, 2,5, 10, 20, 50, 100, 200, 500 (nghìn đồng). Số lượng tờ tiền mỗi mệnh giá là vô hạn. Khách hàng cần rút số tiền $S$ (nghìn đồng). Hãy tìm cách trả tiền sao chotổng số tờ tiền phải trả là ít nhất.

Dữ liệu vào

Một số nguyên dương $S$ là số tiền cần rút ($S$ là bội của 1).

Dữ liệu ra

Tổng số lượng tờ tiền ít nhất cần sử dụng.

Ví dụ