Tại ngân hàng có các mệnh giá: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000. Tổng số tiền cần đổi có giá trị bằng N. Hãy xác định số tờ tiền ít nhất sau khi đổi.

Input

Dòng duy nhất chứa số nguyên N.

Constraints

1 ≤ N ≤ 10^9

Output

Một số nguyên duy nhất: số tờ tiền tối thiểu.

Sample Input

138

Sample Output

6

Giải thích Đổi 138 có thể dùng các tờ: 100 + 20 + 10 + 5 + 2 + 1 → tổng 6 tờ.