Bạn có các đồng xu mệnh giá $1, 2, 5, 10, 20, 50, 100, 200, 500$ (đơn vị nghìn đồng), mỗi loại có số lượng không giới hạn. Hãy trả lại đúng số tiền $S$ bằng số đồng xu ít nhất.

Với bộ mệnh giá này, chiến lược tham lam (luôn dùng đồng lớn nhất không vượt quá số còn lại) cho kết quả tối ưu. Hãy in ra số đồng xu nhỏ nhất cần dùng.

Ví dụ: $S = 28$ → $20 + 5 + 2 + 1$ , dùng $4$ đồng.

Định dạng đầu vào:
Một dòng duy nhất chứa số nguyên $S$ — số tiền cần trả.
Ràng buộc đầu vào:
$1 \le S \le 10^9$ .
Định dạng đầu ra:
In ra một số nguyên là số đồng xu ít nhất.

Đề bài: [Giải thuật] Số đồng xu ít nhất