The Bus Card

Interview

Time limit1sMemory limit1024 MB

Summary

Given a travel amount K in SEK, find the fewest card top-ups of 100, 200, or 500 SEK that cover at least K.

Level: Easy3 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

You are going to purchase a bus card. It is a refillable card into which cash can be deposited, and then used to ride the bus until the money runs out. You know that you plan to travel for $K$ Swedish crowns (SEK). Charging the card takes some time, since you can only charge it with $100$ , $200$ , or $500$ SEK at a time.

You are in a hurry, so you want to make as few transactions as possible, but you never insert more money than necessary. If you are to travel for $800$ SEK, you should load $500$ , then $200$ , and then $100$ SEK. If you are traveling for $850$ SEK, you should first load $500$ , and then $200$ SEK twice. $50$ SEK is wasted, but that is still the best option.

Compute the minimum number of transactions necessary.

Input

The input consists of the integer $K$ ( $1 \le K \le 10\,000$ ), the amount you will travel for.

Output

Output a single integer, the number of transactions necessary.

Examples2

Example 1
Input
```
850
```
Expected output
```
3
```
Example 2
Input
```
1800
```
Expected output
```
5
```