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

To check your solution you need to sign in
Sign in to continue