#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 10 | 1s | 32MB | Minimum |

2 | 15 | 10 | 1s | 32MB | Minimum |

3 | 25 | 10 | 1s | 32MB | Minimum |

4 | 50 | 10 | 1s | 32MB | Minimum |

5 | 0 | 2 | 1s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o lifttokens -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512