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:
n = int(input().strip())

a = {}
temp = {}


def decom(i):
    if i == 0:
        return 0
    if i == 1:
        return 1
    if i in a.keys():
        return a[i]
    if i in temp:
        return decom(i - lower(i)[0]) + lower(i)[1]
    else:
        temp[i] = 0
        k = min(decom(i - lower(i)[0]) + lower(i)[1], decom(upper(i)[0] - i) + upper(i)[1])
        a[i] = k
        return k



def upper(i):
    d = 1
    n = 1
    while d < i:
        d = d * 10 + 1
        n += 1
    return (d, n)


def lower(i):
    if (upper(i)[0] - 1) // 10 == 0:
        return (1, 1)
    return ((upper(i)[0] - 1) // 10, upper(i)[1] - 1)


print(decom(n))