Problem: You are given a positive (greater than zero) integer n.

You have to represent n as the sum of integers (possibly negative) consisting only of ones (digits '1'). For example, 24 = 11 + 11 + 1 + 1 and 102 = 111 - 11 + 1 + 1. 

Among all possible representations, you have to find the one that uses the minimum number of ones in total.

Input

The single line contains one integer n (1 ≤ n < 10^{50}).

Output

Print one integer x — the minimum number of ones, such that there exist a representation of n as the sum of integers (possibly negative) that uses x ones in total.

Examples

Input


24


Output


6


Input


102


Output


7

Solution (in PYTHON3):

Solution:
from heapq import heappush, heappop
from collections import defaultdict

n = int(input())

order = []
heappush(order, (0, n))
have = set()
dist = defaultdict(lambda: 0x3f3f3f3f)
while True:
  d, u = heappop(order)
  if u == 0:
    print(d)
    break
  if u in have:
    continue

  have.add(u)
  sz = len(str(u))

  tens, ones = 1, 0
  while tens <= u:
    ones += tens
    tens *= 10

  add = abs(u - ones)
  if d + sz < dist[add]:
    dist[add] = d + sz
    heappush(order, (d + sz, add))

  sub = abs(ones + tens - u)
  if d + sz + 1 < dist[sub]:
    dist[sub] = d + sz + 1
    heappush(order, (d + sz + 1, sub))