Tại ngân hàng có các mệnh giá tiền:

~1, 2, 5, 10, 20, 50, 100, 200, 500, 1000~

Số lượng tờ tiền của mỗi mệnh giá là không hạn chế.

Một người cần đổi số tiền có giá trị bằng ~N~.

Yêu cầu

Hãy xác định số tờ tiền ít nhất cần dùng để có tổng giá trị bằng ~N~.

Dữ liệu vào

Gồm một số nguyên ~N~.

Ràng buộc

• ~1 ≤ N ≤ 10^14~.

Kết quả

In ra số lượng tờ tiền ít nhất có tổng bằng ~N~.

Ví dụ

Dữ liệu vào

121

Kết quả

3

Giải thích

Ta có thể đổi ~121~ thành:

~100 + 20 + 1~

Vậy cần ít nhất ~3~ tờ tiền.