Hundraelva kronor

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, find the fewest notes with values 1, 11, 111, ... that sum exactly to N.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Greedy, Number theory
Solved: No attempts yet

Problem

At the Tumba paper mill, which is responsible for producing banknotes, the printing press has broken down: it can now print only the digit "1". Buying a new press costs $N$ kronor, but the mill has run out of money entirely. Since the mill itself prints banknotes, why not print new money so it can buy the new machine?

Because the broken press can print only the digit "1", it can produce only notes with values 1 krona, 11 kronor, 111 kronor, 1111 kronor, and so on.

The mill wants to know how many notes it needs to print to pay for the new press. It must pay with exact change, that is, exactly $N$ kronor (printing more money than needed is immoral), and it wants to print as few notes as possible. Write a program that computes the number of notes it must print.

Input

An integer $N$ ( $1 \le N \le 1\,000\,000\,000$ ), the cost in kronor of the new printing press.

Output

Print an integer: the minimum number of notes that need to be printed.

Hint

In the first sample case, one 1-krona note and two 11-krona notes can be used.
In the second sample case, one note of each of 1, 11, 111, 1111, and 11111 kronor can be used.

Examples3

Example 1
Input
```
23
```
Expected output
```
3
```
Example 2
Input
```
12345
```
Expected output
```
5
```
Example 3
Input
```
282828
```
Expected output
```
28
```