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.

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

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

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.

Sample Input 1 | Sample Output 1 |
---|---|

850 |
3 |

Sample Input 2 | Sample Output 2 |
---|---|

1800 |
5 |