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 ones(a):
    return (10 ** a - 1) // 9

def add_in_dict(dct, key, val):
    if key in dct:
        dct[key] = min(dct[key], val)
    else:
        dct[key] = val
    
_s = input()
_n = len(_s)
_x = int(_s)

cur_dict = {}
cur_dict[_x] = 0

for i in range(_n + 1, 0, -1):
    ns = ones(i)
    new_dict = {}
    for x in cur_dict:
        v = cur_dict[x]

        while ns <= x:
            x -= ns
            v += i

        add_in_dict(new_dict, x, v)
        add_in_dict(new_dict, ns - x, v + i)

    cur_dict = new_dict

print(cur_dict[0])