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
ones = [1]
for i in range(1, 52):
    ones.append(ones[-1] * 10 + 1)


def solve(n, cache={}):
    if n == 0: return 0
    if n in cache: return cache[n]

    x = None
    for v in ones:
        if v <= n:
            x = v

    y = x * 10 + 1
    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]


def main():
    n = int(input())
    print(solve(n))


if __name__ == '__main__':
    main()
