Một hệ thống tiền tệ có các mệnh giá: 1, 2, 5, 10, 20, 50, 100, 200, 500. Cho số tiền \(N\).

Yêu cầu:

Hãy tìm số tờ tiền ít nhất để có tổng bằng \(N\).

Input:

Một số nguyên duy nhất \(N\) (\(1 \le N \le 10^9\)).

Output:

Một số nguyên là số tờ tiền ít nhất.

125

3 (gồm 1 tờ 100, 1 tờ 20, 1 tờ 5).