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:
def solve(n, cache={}):
    if n == 0: return 0
    if n in cache: return cache[n]

    v = 0
    while v <= n:
        x = v
        v = v * 10 + 1
        y = v

    res1 = (n // x) * len(str(x)) + solve(n % x)
    res2 = len(str(y)) + solve((y - n) % x) + ((y - n) // x) * len(str(x))
    
    cache[n] = min(res1, res2)
    return cache[n]

n = int(input())
print(solve(n))