付款

题目描述

AtCoder 王国的货币只有 $10^{100}+1$ 种面额的纸币,价值分别为 $1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}$。你想在商店街买 $1$ 台价值 $N$ 的章鱼烧机。

你决定支付不小于 $N$ 的金额。之后,店员会支付正好比你支付的金额少 $N$ 的金额作为找零。

当你和店员合理地选择所用的纸币组合时,两人所用纸币的总数最少是多少张?

另外,假设你和店员都拥有任意面额的纸币,且数量足够多。

输入格式

输入按以下格式从标准输入给出:

$N$

输出格式

输出支付的纸币张数与作为找零收到的纸币张数之和的最小值。

样例

36

8

你支付 $4$ 张面额 $10$ 的纸币,店员找给你 $4$ 张面额 $1$ 的纸币,所用纸币总数合计为 $8$ 张。

无法用少于 $8$ 张的总张数完成,所以答案是 $8$。

91

3

你支付 $1$ 张面额 $100$ 的纸币和 $1$ 张面额 $1$ 的纸币,店员找给你 $1$ 张面额 $10$ 的纸币,所用纸币总数合计为 $3$ 张。

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

243

数据范围

• $N$ 是 $1$ 以上 $10^{1,000,000}$ 以下的整数