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.