No.636 硬貨の枚数2
しらっ亭
はむこ問題文
YUKI国には、任意の非負整数 $k$ に対して、額面が $1 \times 10^k$ 円と $5 \times 10^k$ 円であるような硬貨が流通しています。
流通している硬貨を額面を小さい方からいくつか列挙すると、$1, 5, 10, 50, 100, 500, \dots $ です。
雪子さんは、お店で $N$ 円の品物を購入しようと思っています。
$N$ 円の決済をするのに、YUKI国の硬貨で $X (X \ge N)$ 円をお店に支払い、お釣りとしてYUKI国の硬貨で $X-N$ 円を受け取ります。
決済で硬貨を支払うときも、お釣りとして受け取るときも、枚数が最小となるように硬貨を選んでやり取りを行います。
雪子さんもお店も、全ての額面の硬貨を $10^{10000}$ 枚持っているため、やり取りのときに硬貨が不足してしまうことはありません。
雪子さんは、やり取りする硬貨の枚数、つまり、"渡す硬貨の枚数と受け取る硬貨の枚数の和" を最小化したいです。
やり取りする硬貨の枚数の最小値を求めてください。
入力
N
$1 \le N \le 10^{10000}$
$N$ は整数。
$N$ は 32bit 整数型や 64bit 整数型に収まらない可能性がある点に注意してください。
出力
答えを1行で出力してください。最後に改行してください。
サンプル
サンプル1
入力
87
出力
5
例えば、$87$ 円の決済に、$102$ 円を渡して $15$ 円を受け取ります。
額面 $100, 1, 1$ の $3$ 枚の硬貨を渡し、額面 $10, 5$ の $2$ 枚を受け取ることで、やり取りする硬貨の枚数は $5$ 枚となり、これが最小です。
サンプル2
入力
1343414
出力
11
例えば、$1500015$ 円を渡し、$156601$ 円を受け取ります。渡す硬貨 $4$ 枚と受け取る硬貨 $7$ 枚で合計 $11$ 枚のやり取りとなり、これが最小です。
サンプル3
入力
175
出力
5
$100, 50, 10, 10, 5$ と支払ってお釣りをゼロにする方法と、$100, 100$ と支払ってお釣りを $10, 10, 5$ にする方法があり、いずれも $5$ 枚のやり取りとなり、これが最小です。
サンプル4
入力
5000000000000000
出力
1
$1$ 枚で支払いが可能です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。