Problem H
Bus Card

You are buying a transit bus card. It is a reloadable card that you can charge with cash. Afterwards, you can use it until it runs out of money.

You know that you are supposed to make trips for $K$ dollars, where $K \leq 10\, 000$. Charging the card takes some time, since you can only charge it with $500$, $200$ or $100$ dollars at a time. Since you are in a hurry, you want to charge it as few times as possible, but never with more money than necessary.

If you want to travel for $800$ dollars, you want to charge the card first with $500$ dollars, then $200$ dollars and finally with $100$ dollars. If you want to travel for $850$ dollars, you first need to charge it with $500$ dollars and then charge it with $200$ dollars twice. You will waste $50$ dollars, but it is still the best alternative (you cannot waste less).

Write a program that computes the least number of times you need to charge the card.

Input

The input contains an integer $1 \le K \le 10\, 000$, the number of dollars you want to charge the card with.

Output

Your program should output a single integer; the least number of transactions you need to do.

Scoring

Your program will be tested on three test cases. If you pass two of them, you get $50$ points. If you pass three of them, you get $100$ points.

850

3

1800

5