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:
MAX_CNT = 6
X = int(input())
N = len(str(X))

NUMBERS = [0] * (N + 2)
CUTOFFS = [0] * (N + 2)

for d in range(1, N + 2):
    NUMBERS[d] = 10 * NUMBERS[d - 1] + 1
    CUTOFFS[d] = 10**(d - 1) * 50 // 81 + 15

INF = 10**9
save = [{} for d in range(N + 2)]

def recurse(value, d):
    if d == 0:
        return 0 if value == 0 else INF

    if value in save[d]:
        return save[d][value]

    ans = INF

    for cnt in range(0, MAX_CNT + 1):
        nvalue = abs(value - cnt * NUMBERS[d])

        if nvalue <= CUTOFFS[d]:
            ans = min(ans, cnt * d + recurse(nvalue, d - 1))

    save[d][value] = ans
    return ans

print(recurse(X, N + 1))