Competitions
Сортировка и жадность - 2
Cash machine
The cash machine contains the sufficient number of banknotes with denominations 10, 20, 50, 100, 200 and 500 hryvnias. Find the minimum number of bills to give an amount of n hryvnias or print -1 if its impossible.
Input data
One integer n (1 ≤ n ≤ 10^6).
Output data
Print the minimum number of banknotes to give n hryvnias or -1 if its impossible.
Examples
Input example #1
770
Output example #1
4
Note
The sum of 770 hryvnia can be given as follows: 500 + 200 + 50 + 20.