Đề bài

Tại ngân hàng của Hoà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

Giới hạn : 1 ≤ N ≤ 10⁹.

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ờ.