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

```18
```

```2
```

```20
```

```2
```