C - Security 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

AtCoder 社の入口には特殊なパスコード入力装置があり、 この装置は文字列を 1 つ表示する画面と 2 つのボタンからなります。

画面に表示される文字列を t とします。 t ははじめ空文字列であり、ボタンを押すことで t に以下の変化が起きます。

  • ボタン A を押すと、t の末尾に 0 が追加される。
  • ボタン B を押すと、t に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、0 から 8 までの数字については次の数字は 1 大きな数を表す数字とし、9 の次の数字は 0 とする。

たとえば、t が 1984 のときにボタン A を押すと t は 19840 に変化し、さらにボタン B を押すと t は 20951 に変化します。

文字列 S が与えられます。t が空文字列である状態からボタンを 0 回以上押して t を S に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。

制約

  • S は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる文字列
  • 1 \leq |S| \leq 5 \times 10^5 (|S| は S の長さをあらわす)

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

21

出力例 1

4

以下の順にボタンを押せば、t が 21 になります。

  1. ボタン A を押す。t は 0 になる。
  2. ボタン B を押す。t は 1 になる。
  3. ボタン A を押す。t は 10 になる。
  4. ボタン B を押す。t は 21 になる。

4 回より少ない回数ボタンを押して t を 21 にすることはできないので、4 を出力します。

入力例 2

407

出力例 2

17

入力例 3

2025524202552420255242025524

出力例 3

150

Score : 300 points

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

  • Pressing button A appends 0 to the end of t.
  • Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

  • S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
  • 1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Input

The input is given from Standard Input in the following format:

S

Output

Output the answer.

Sample Input 1

21

Sample Output 1

4

The following sequence of presses makes t equal to 21.

  1. Press button A. t becomes 0.
  2. Press button B. t becomes 1.
  3. Press button A. t becomes 10.
  4. Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

407

Sample Output 2

17

Sample Input 3

2025524202552420255242025524

Sample Output 3

150