## 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