Simple Coin Change
There are 6 types of coins in Armenia. Each one has a different value. The values are 10, 20, 50, 100, 200, and 500. You are at a store and would like to pay the bill with the minimum number of coins. Can you write a program to calculate the minimum number of coins required to pay the bill?
Input
The only line of the input contains a single integer
b (10 ≤ b ≤ ) - the amount you need to pay at the store.Output
The program should print the minimum number of coins you can use to pay it.
Examples
Input | Output |
30 | 2 |
90 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB