Minh go shopping at the SS shop. The shop has currency denominations: ~1$, 5$, 10$, 50$, 100$, 500$~.

Minh takes some items at the shop and pay an amount of ~1000$~. Your task to devise a method to pay back amount to customer using fewest number of money notes.

Input

The input consists of only one single integer ~N~ ~(1 \le N \le 999)~ denoting the total value of the taken items.

Output

The output consists of only one single integer denoting the number of money notes.

Example

Input

380

Output

4

Explanation

The shop has to pay back ~620$~ by giving one paper of ~500$~, one paper of ~100$~ and two papers of ~10$~.