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 = {}
def decom(i):
    if i == 0:        return 0
    if i == 1:        return 1
    if i in a.keys():        return a[i]
    if upper(i)[0] - i > i:  return decom(i - lower(i)[0]) + lower(i)[1]
    else: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))