e-olymp
Competitions

жадібний алгоритм

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

One integer n (1n106).

Output

Print the minimum number of banknotes to give n hryvnias or -1 if its impossible.

Explanation

The sum of 770 hryvnia can be given as follows: 500 + 200 + 50 + 20.

Time limit 1 second
Memory limit 128 MiB
Input example #1
770
Output example #1
4