101554: [AtCoder]ABC155 E - Payment

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score: $500$ points

Problem Statement

In the Kingdom of AtCoder, only banknotes are used as currency. There are $10^{100}+1$ kinds of banknotes, with the values of $1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}$. You have come shopping at a mall and are now buying a takoyaki machine with a value of $N$. (Takoyaki is the name of a Japanese snack.)

To make the payment, you will choose some amount of money which is at least $N$ and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus $N$.

What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?

Assume that you have sufficient numbers of banknotes, and so does the clerk.

Constraints

  • $N$ is an integer between $1$ and $10^{1,000,000}$ (inclusive).

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the minimum possible number of total banknotes used by you and the clerk.


Sample Input 1

36

Sample Output 1

8

If you give four banknotes of value $10$ each, and the clerk gives you back four banknotes of value $1$ each, a total of eight banknotes are used.

The payment cannot be made with less than eight banknotes in total, so the answer is $8$.


Sample Input 2

91

Sample Output 2

3

If you give two banknotes of value $100, 1$, and the clerk gives you back one banknote of value $10$, a total of three banknotes are used.


Sample Input 3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

Sample Output 3

243

Input

题意翻译

## 题目描述 给定正整数 $N$,设 $f(x)$ 表示 $x$ 在十进制下各个数位上的数的和,求一个正整数 $x$ 满足 $x\ge N$ 且最小化 $f(x)+f(x-N)$。 ## 数据范围 $1\le N\le10^{1000000}$。 ## 输入输出格式 ### 输入格式 一行一个正整数 $N$,含义如题所述。 ### 输出格式 一行一个正整数 $ans$,表示最小的 $f(x)+f(x-N)$。

加入题单

上一题 下一题 算法标签: