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 PYTHON):

Solution:
from collections import deque
n = input()
cost = {}

def ones(x):
	ans = 0
	for i in range(x):
		ans *= 10
		ans += 1
	return ans

def numdigits(x):
	tmp = x
	ans = 0
	while (tmp != 0):
		ans += 1
		tmp /= 10
	return ans

cost[n] = 0
length = numdigits(n)

for cur_digits in range(length, 0, -1):
	#remove nodes corresponding to numbers with more than cur_digits
	cost = {key:val for key,val in cost.items() if key <= ones(cur_digits+1)}

	#now relax edges
	q = deque()
	d = ones(cur_digits)
	dd = ones(cur_digits+1)

	for key, val in cost.items():
		q.append((key,val))

	while len(q) != 0:
		cur_num, cur_cost = q.popleft()


		tmp_num = cur_num - d
		if tmp_num >= 0:
			if (tmp_num not in cost) or (cost[tmp_num] > cur_cost + cur_digits):
				cost[tmp_num] = cur_cost + cur_digits
				q.append((tmp_num, cost[tmp_num]))
				#print(tmp_num, cost[tmp_num])

		tmp_num = dd - cur_num
		if (tmp_num not in cost) or (cost[tmp_num] > cur_cost + cur_digits):
			cost[tmp_num] = cur_cost + cur_digits +1
			q.append((tmp_num, cost[tmp_num]))
			#print(tmp_num, cost[tmp_num])

print(cost[0])