German Conference for Public Counting

Interview

Time limit1sMemory limit1024 MB

Summary

Given n, find the fewest digit signs needed so every number from n down to 0 can be displayed with them.

Level: Medium5 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Greta loves counting. She practises it every day of the year. Depending on the season, she counts falling leaves, raindrops, snowflakes, or even growing leaves. However, there is one event in summer which tops everything else: the German Conference for Public Counting (GCPC).

At this event, Greta meets counting enthusiasts from all over the country for one week of counting and counting and counting... Together they participate in the Glamorous Competitive Public Counting and the Great Chaotic Public Counting. At the end of the week they all try to win the Golden Cup of Public Counting. Her favourite is the Gently Calming Public Counting where the crowd counts in silence, trying to harmoniously synchronise to reach the target number at precisely the same moment.

Figure G.1: People holding up signs for the countdown.

To increase the tension and to prepare for the Gently Calming Public Counting, the organizers of GCPC plan to start with a silent countdown, where the people on the stage will at any time display the current number by holding up signs with its digits. On every sign, there is exactly one decimal digit. Numbers greater than $9$ are displayed by holding up several signs next to each other. Each number is shown using the least possible number of signs; there is no left padding with zeroes. This way, the people on the stage display numbers $n, n-1, n-2, \dots$ until they finally display $0$ . Since the GCPC will take place soon, the organizers want to finish their preparations quickly. How many signs do they need to prepare at least so that they can display the entire countdown from $n$ to $0$ ?

Input

The input consists of:

One line with an integer $n$ ( $1 \le n \le 10^9$ ), the starting number of the countdown.

Output

Output the minimum number of signs required to display every number of the countdown.

Hint

In the first sample case, the organizers need one sign each with the digits $0$ to $5$ , for a total of $6$ signs. In the second sample case, they need one sign with each digit other than $1$ , and two signs with a $1$ , for a total of $9+2=11$ signs.

Examples5

Example 1
Input
```
5
```
Expected output
```
6
```
Example 2
Input
```
20
```
Expected output
```
11
```
Example 3
Input
```
44
```
Expected output
```
14
```
Example 4
Input
```
271828182
```
Expected output
```
82
```
Example 5
Input
```
314159265
```
Expected output
```
82
```