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:

import math
from collections import defaultdict

n = input()

opt = defaultdict(lambda: 1e9)

def calc(s, cost):

    if cost >= opt[s]:
        return 1e9
    opt[s] = cost

    if cost + min(int(s[0]),4)*len(s) > opt['0']:
        return 1e9

    if s=='0':
        return cost
    
    if s[0]<'4':
        return calc( str(abs(int(s) - int('1'*len(s)))), cost + len(s))
    
    if s[0]>'6':
        return calc( str(int('1'*(len(s)+1)) - int(s)), cost + len(s)+1)


    a = calc( str(abs(int(s) - int('1'*len(s)))), cost + len(s))
    b = calc( str(int('1'*(len(s)+1)) - int(s)), cost + len(s)+1)

    return min(a,b)

calc(n,0)

print(opt['0'])