Ice Cream Stick Game

There is a row of ice cream sticks. Each stick has a single digit from $0$ to $9$ written on it, and the digit on the leftmost stick is nonzero. Together, reading from left to right, they form a positive decimal integer $n$.

CatCat wants to make $n$ become $0$ (i.e. remove all sticks) using as few operations as possible, because she thinks that $0$ is beautiful. CatCat performs the following operation repeatedly:

1. Choose any stick whose digit is nonzero and subtract $1$ from that digit.
2. After the subtraction, if there is a sequence of consecutive sticks at the beginning whose digits are $0$ (i.e. there is a leading zero sequence), then remove all these sticks from the row.

At some moment (possibly before any of CatCat’s operations or after any one of them), a mischievous Mouse will come and change the digit on exactly one of the sticks to any other digit (from $0$ to $9$). Mouse wants CatCat to perform as many operations as possible while CatCat wants to minimize the number of operations. Assuming both play optimally, compute the final number of operations CatCat will perform.

Note: Every subtraction counts as one operation. Even if a stick is eventually removed because it becomes part of a leading block of zeros, each subtraction performed is counted.

inputFormat

The input consists of a single line containing a positive decimal integer n without any spaces. The number is given by its digits (the leftmost digit is nonzero) and may be very large.

outputFormat

Output a single integer, which is the minimum number of operations CatCat will make under optimal play by both CatCat and the Mouse.

Explanation of the optimal strategies:

If Mouse does not make a change, CatCat’s optimal strategy is to always subtract from the leftmost nonzero digit until it becomes $0$ (thus causing removal of the leading zero block), then proceed with the next digit. In this case, the total number of operations is exactly the sum of the digits of n.

Mouse, however, can change exactly one digit (at the very beginning, before any subtraction takes place) to maximize the number of operations by increasing that digit to $9$. Since every digit will eventually have to be reduced to $0$, Mouse’s best move is to pick the digit for which the increase $(9-d)$ is maximized. Hence, the final number of operations becomes:

$\text{answer} = \Bigl(\sum_{i=0}^{m-1} d_i \Bigr) + \max_{0 \le i < m} (9-d_i)$

sample

12

11