Problem Description
Rar the Cat is stuck at floor N of a very very tall building. In order to get down back to floor 0, he needs to purchase "lift tokens". Each lift token can bring him down a certain number of levels. For example, a lift token that is of type 5 will bring him down 5 levels, say, from level 6 to level 1.
There are many types of lift tokens that can bring Rar the Cat down a number of levels, namely 1, 5, 10, 17, 50, 100, 500, 1000, 5000 and 10000 levels. Each lift token costs 1 dollar. Given N, which is the floor that Rar the Cat is stuck on, output the minimum number of dollars Rar the Cat has to spend in getting down.
Input
The first line of input will consist of one integer, N.
Output
The output should contain one line with one integer, the minimum number of dollars needed to bring Rar the Cat down to EXACTLY floor 0.
Limits
Subtask 1 (10%): 1 ≤ N ≤ 10
Subtask 2 (15%): 1 ≤ N ≤ 1000
Subtask 3 (25%): 1 ≤ N ≤ 1000000
Subtask 4 (50%): 1 ≤ N ≤ 1000000000
Sample Input 1
18
Sample Output 1
2
Sample Input 2
20
Sample Output 2
2