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 \le 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


-----Note-----

None

Difficulty: VERY_HARD
Tags: Greedy algorithms

Dynamic programming

Shortest paths
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def ones(a):
	return (10 ** a - 1) // 9

def add_in_dict(dct, key, val):
	if key in dct:
		dct[key] = min(dct[key], val)
	else:
		dct[key] = val
_s = input()
_n = len(_s)
_x = int(_s)
cur_dict = {}
cur_dict[_x] = 0
for i in range(_n + 1, 0, -1):
	ns = ones(i)
	new_dict = {}
	for x in cur_dict:
		v = cur_dict[x]
		while ns <= x:
			x -= ns
			v += i
		add_in_dict(new_dict, x, v)
		add_in_dict(new_dict, ns - x, v + i)
	cur_dict = new_dict
print(cur_dict[0])


memo = {}

def solve(n):
	if n <= 6:
		return n
	elif n <= 11:
		return 2 + (11 - n)
	elif n in memo:
		return memo[n]
	else:
		digits = [int(c) for c in str(n)]
		s = len(digits)
		Ln = 10 ** s // 9
		if n == Ln:
			return s
		if n < Ln:
			Ln = Ln // 10
			s -= 1
		Un = 10 * Ln + 1
		len1 = solve(n % Ln) + s * (n // Ln)
		n2 = Un - n
		len2 = solve(n2 % Ln) + s * (n2 // Ln) + s + 1
		ans = min(len1, len2)
		memo[n] = ans
		return ans
n = int(input())
print(solve(n))


DIGITS = 55
MAX_CNT = 6
NUMBERS = [0] * (DIGITS + 1)
CUTOFFS = [0] * (DIGITS + 1)
for d in range(1, DIGITS + 1):
	NUMBERS[d] = 10 * NUMBERS[d - 1] + 1
	CUTOFFS[d] = 10 ** (d - 1) * 50 // 81 + 15
INF = 10 ** 9
save = [{} for d in range(DIGITS)]

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
X = int(input())
print(recurse(X, len(str(X)) + 1))


import sys

def solve(N):
	strN = str(N)
	no_digits = len(strN)
	res_list = []
	if int(strN[0]) < 8:
		res_list.append((0, N))
	if int(strN[0]) > 4:
		felso = int('1' * (no_digits + 1))
		res_list.append((no_digits + 1, felso - N))
	for i in range(no_digits):
		res_list_copy = [r for r in res_list]
		res_list = []
		my_num = no_digits - i
		oneone = int('1' * my_num)
		for (steps, remainder) in res_list_copy:
			also = remainder // oneone
			felso = also + 1
			res_list.append((steps + also * my_num, remainder - oneone * also))
			res_list.append((steps + felso * my_num, oneone * felso - remainder))
		steps = [s[0] for s in res_list]
		step_min = min(steps)
		step_max = (my_num + 1) * 6 + step_min
		res_list = [r for r in res_list if r[0] < step_max]
	res_list = [x - i for (x, i) in res_list]
	return min(res_list)

def run():
	out = ''
	N = int(input())
	print(solve(N))
run()


def ans(n):
	if n == 0:
		return 0
	val = 1
	ct = 1
	while 10 * val + 1 <= n:
		val *= 10
		val += 1
		ct += 1
	if n <= 5 * val:
		return ans(n - val) + ct
	if n > 6 * val:
		return ans(10 * val + 1 - n) + ct + 1
	ans1 = ans(n - val) + ct
	ans2 = ans(10 * val + 1 - n) + ct + 1
	return min(ans1, ans2)
n = int(input())
print(ans(n))


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


import math
from collections import defaultdict
n = input()
opt = defaultdict(lambda : 1000000000.0)

def calc(s, cost):
	if cost >= opt[s]:
		return 1000000000.0
	opt[s] = cost
	if cost + min(int(s[0]), 4) * len(s) > opt['0']:
		return 1000000000.0
	if s == '0':
		return cost
	if s[0] < '6':
		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'])


n = int(input())
dp = {}

def calc(x):
	if 0 == x:
		return 0
	if x in dp.keys():
		return dp[x]
	l = len(str(x))
	u = 10 ** l // 9
	if x < u:
		u = u // 10
		l -= 1
	v = u * 10 + 1
	u1 = calc(x % u) + x // u * l
	u2 = calc((v - x) % u) + (l + 1) + (v - x) // u * l
	res = min(u1, u2)
	dp[x] = res
	return res
print(calc(n))


n = int(input())
res = {}

def cal(x):
	if x == 0:
		return 0
	if x in res.keys():
		return res[x]
	larger = 1
	while x >= larger:
		larger = larger * 10 + 1
	smaller = larger // 10
	l = len(str(smaller))
	a = cal(x % smaller) + x // smaller * l
	b = cal((larger - x) % smaller) + l + 1 + (larger - x) // smaller * l
	res[x] = min(a, b)
	return res[x]
print(cal(n))


class Segment:

	def __init__(self, start, values):
		self.start = start
		self.values = values

	def __repr__(self):
		return repr((self.start, self.values))

	def get(self, i):
		if i < self.start or self.start + len(self.values) <= i:
			return None
		return self.values[i - self.start]

def one(n):
	return (10 ** n - 1) // 9
INF = 10 ** 100

def merge(segs):
	result = []
	s = -1
	new_seg = Segment(-1, [])
	while True:
		minv = INF
		for seg in segs:
			v = seg.get(s)
			if v is not None:
				minv = min(minv, v)
		if minv == INF:
			if new_seg.values:
				result.append(new_seg)
			ns = INF
			for seg in segs:
				if s < seg.start:
					ns = min(ns, seg.start)
			if ns == INF:
				break
			s = ns
			new_seg = Segment(s, [])
		else:
			new_seg.values.append(minv)
			s += 1
	return result

def solve(n):
	pos = [Segment(n, [0])]
	neg = []
	for length in range(len(str(n)) + 1, 0, -1):
		pre_one = one(length + 1)
		cur_one = one(length)
		new_pos = []
		new_neg = []
		for seg in pos:
			s = seg.start
			k = s // cur_one
			r = s % cur_one
			new_pos_seg = Segment(r, [])
			new_neg_seg = Segment(r, [])
			for v in seg.values:
				new_pos_seg.values.append(v + k * length)
				new_neg_seg.values.append(v + (k + 1) * length)
				if r + 1 == cur_one:
					new_pos.append(new_pos_seg)
					new_neg.append(new_neg_seg)
					k += 1
					r = 0
					new_pos_seg = Segment(0, [])
					new_neg_seg = Segment(0, [])
				else:
					r += 1
			if new_pos_seg.values:
				new_pos.append(new_pos_seg)
				new_neg.append(new_neg_seg)
		for seg in neg:
			s = pre_one - seg.start
			k = (pre_one - seg.start - 1) // cur_one
			r = (seg.start - pre_one) % cur_one
			new_pos_seg = Segment(r, [])
			new_neg_seg = Segment(r, [])
			for v in seg.values:
				new_neg_seg.values.append(v + k * length)
				new_pos_seg.values.append(v + (k + 1) * length)
				if r + 1 == cur_one:
					new_pos.append(new_pos_seg)
					new_neg.append(new_neg_seg)
					r = 0
					k -= 1
					new_pos_seg = Segment(0, [])
					new_neg_seg = Segment(0, [])
				else:
					r += 1
			if new_pos_seg.values:
				new_pos.append(new_pos_seg)
				new_neg.append(new_neg_seg)
		pos = merge(new_pos)
		neg = merge(new_neg)
	assert pos
	assert pos[0].start == 0
	return pos[0].values[0]
while True:
	try:
		n = int(input())
	except EOFError:
		break
	print(solve(n))


def solve(n, cache={}):
	if n == 0:
		return 0
	if n in cache:
		return cache[n]
	v = 0
	while v <= n:
		x = v
		v = v * 10 + 1
		y = v
	res1 = n // x * len(str(x)) + solve(n % x)
	res2 = len(str(y)) + solve((y - n) % x) + (y - n) // x * len(str(x))
	cache[n] = min(res1, res2)
	return cache[n]
n = int(input())
print(solve(n))


import sys

def read_ints():
	return [int(i) for i in sys.stdin.readline().strip().split()]

def read_int():
	return int(sys.stdin.readline().strip())
CACHE = {}

def n_ones(n):
	if n < 5:
		return n
	if n in CACHE:
		return CACHE[n]
	n = abs(n)
	s = str(n)
	ones = int('1' * len(s))
	dig = int(s[0])
	guess = ones * dig
	if n == ones:
		return len(s)
	elif guess <= n:
		below = guess
		if dig == 9:
			above = int('1' * (len(s) + 1))
		else:
			above = guess + ones
	else:
		above = guess
		if dig == 1:
			below = int('9' * (len(s) - 1))
		else:
			below = guess - ones
	above_digit = int(str(above)[0])
	below_digit = int(str(below)[0])
	below_ones = below_digit * len(str(below)) + n_ones(n - below)
	above_ones = above_digit * len(str(above)) + n_ones(above - n)
	result = min(below_ones, above_ones)
	if dig > 5:
		above2 = int('1' * (len(s) + 1))
		above2_digit = int(str(above2)[0])
		above2_ones = above2_digit * len(str(above2)) + n_ones(above2 - n)
		result = min(result, above2_ones)
	CACHE[n] = result
	return result
n = read_int()
print(n_ones(n))


DIGITS = 55
MAX_CNT = 6
CUTOFF_RATIO = 0.618
NUMBERS = [0] * (DIGITS + 1)
CUTOFFS = [0] * (DIGITS + 1)
for d in range(1, DIGITS + 1):
	NUMBERS[d] = 10 * NUMBERS[d - 1] + 1
	CUTOFFS[d] = CUTOFF_RATIO * 10 ** (d - 1) + 15
X = int(input())
N = int(len(str(X)))
candidates = {X: 0}
for d in range(N + 1, 0, -1):
	ncandidates = {}

	def insert(value, cost):
		if value not in ncandidates or cost < ncandidates[value]:
			ncandidates[value] = cost
	for value in candidates:
		cost = candidates[value]
		for cnt in range(MAX_CNT + 1):
			nvalue = abs(value - cnt * NUMBERS[d])
			if nvalue <= CUTOFFS[d]:
				insert(nvalue, cost + cnt * d)
	candidates = ncandidates
print(candidates[0])


ones = [1]
for i in range(1, 52):
	ones.append(ones[-1] * 10 + 1)

def solve(n, cache={}):
	if n == 0:
		return 0
	if n in cache:
		return cache[n]
	x = None
	for v in ones:
		if v <= n:
			x = v
	y = x * 10 + 1
	res1 = n // x * len(str(x)) + solve(n % x)
	res2 = len(str(y)) + solve((y - n) % x) + (y - n) // x * len(str(x))
	cache[n] = min(res1, res2)
	return cache[n]

def main():
	n = int(input())
	print(solve(n))
main()


dp = {}

def solve(x):
	if x == 0:
		return 0
	if x in dp.keys():
		return dp[x]
	limit = 1
	cnt = 1
	while limit <= x:
		limit = limit * 10 + 1
		cnt += 1
	prv = limit // 10
	c1 = solve(x % prv) + x // prv * (cnt - 1)
	c2 = solve((limit - x) % prv) + cnt + (cnt - 1) * ((limit - x) // prv)
	dp[x] = min(c1, c2)
	return min(c1, c2)
n = int(input())
print(solve(n))


from heapq import heappush, heappop
from collections import defaultdict
n = int(input())
order = []
heappush(order, (0, n))
have = set()
dist = defaultdict(lambda : 1061109567)
while True:
	(d, u) = heappop(order)
	if u == 0:
		print(d)
		break
	if u in have:
		continue
	have.add(u)
	sz = len(str(u))
	(tens, ones) = (1, 0)
	while tens <= u:
		ones += tens
		tens *= 10
	add = abs(u - ones)
	if d + sz < dist[add]:
		dist[add] = d + sz
		heappush(order, (d + sz, add))
	sub = abs(ones + tens - u)
	if d + sz + 1 < dist[sub]:
		dist[sub] = d + sz + 1
		heappush(order, (d + sz + 1, sub))


import sys, os
if os.environ['USERNAME'] == 'kissz':
	s = '4897332836602749275099151826428737446171648588383'

	def debug(*args):
		print(*args, file=sys.stderr)
		sys.stderr.flush()
else:
	s = input().strip()

	def debug(*args):
		pass

def sub(x, y):
	n = len(x)
	m = len(y)
	assert n == m
	z = [0] * n
	greater = 0
	for (a, b) in zip(x, y):
		if a > b:
			greater = 1
			break
		elif a < b:
			greater = -1
			break
	if greater == 0:
		return z
	elif greater == -1:
		(x, y) = (y, x)
	c = 0
	for i in range(max(n, m) - 1, -1, -1):
		(a, b) = (x[i], y[i])
		b = b + c
		z[i] = (a - b) % 10
		c = a < b
	return z
x0 = [int(c) for c in s]
while x0[0] == 0:
	x0.pop(0)
x0 = [0] + x0
n = len(x0)
o = 0
best = 1 << 30
visit = 0
Q = [(0, n, x0)]
while Q:
	(r, l, x) = Q.pop()
	visit += 1
	if l == 0:
		debug(best, len(Q), visit)
		continue
	if r >= best:
		continue
	zlim = 9
	for a in range(x[0] - 1, x[0] + 2):
		z = sub([a] * l, x)
		if l == 1 and z[0] == 0:
			best = min(best, r + a)
		elif z[0] == 0 and z[1] <= zlim:
			zlim = z[1]
			Q.append((r + a * l, l - 1, z[1:]))
debug(visit)
print(best)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1

class DualSegmentTree:

	def __init__(self, n, segfunc, ide_ele):
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num

	def update(self, l, r, x):
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				self.tree[l] = self.segfunc(self.tree[l], x)
				l += 1
			if r & 1:
				self.tree[r - 1] = self.segfunc(self.tree[r - 1], x)
			l >>= 1
			r >>= 1

	def __getitem__(self, idx):
		idx += self.num
		res = self.ide_ele
		while idx:
			res = self.segfunc(res, self.tree[idx])
			idx >>= 1
		return res

class LazySegmentTree:
	__slots__ = ['merge', 'merge_unit', 'operate', 'merge_operate', 'operate_unit', 'n', 'data', 'lazy']

	def __init__(self, n, init, merge, merge_unit, operate, merge_operate, operate_unit):
		self.merge = merge
		self.merge_unit = merge_unit
		self.operate = operate
		self.merge_operate = merge_operate
		self.operate_unit = operate_unit
		self.n = (n - 1).bit_length()
		self.data = [merge_unit for i in range(1 << self.n + 1)]
		self.lazy = [operate_unit for i in range(1 << self.n + 1)]
		if init:
			for i in range(n):
				self.data[2 ** self.n + i] = init[i]
			for i in range(2 ** self.n - 1, 0, -1):
				self.data[i] = self.merge(self.data[2 * i], self.data[2 * i + 1])

	def propagate(self, v):
		ope = self.lazy[v]
		if ope == self.operate_unit:
			return
		self.lazy[v] = self.operate_unit
		self.data[v << 1] = self.operate(self.data[v << 1], ope)
		self.data[(v << 1) + 1] = self.operate(self.data[(v << 1) + 1], ope)
		self.lazy[v << 1] = self.merge_operate(self.lazy[v << 1], ope)
		self.lazy[(v << 1) + 1] = self.merge_operate(self.lazy[(v << 1) + 1], ope)

	def propagate_above(self, i):
		m = i.bit_length() - 1
		for bit in range(m, 0, -1):
			v = i >> bit
			self.propagate(v)

	def remerge_above(self, i):
		while i:
			c = self.merge(self.data[i], self.data[i ^ 1])
			i >>= 1
			self.data[i] = self.operate(c, self.lazy[i])

	def update(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.data[l] = self.operate(self.data[l], x)
				self.lazy[l] = self.merge_operate(self.lazy[l], x)
				l += 1
			if r & 1:
				self.data[r - 1] = self.operate(self.data[r - 1], x)
				self.lazy[r - 1] = self.merge_operate(self.lazy[r - 1], x)
			l >>= 1
			r >>= 1
		self.remerge_above(l0)
		self.remerge_above(r0)

	def query(self, l, r):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		res = self.merge_unit
		while l < r:
			if l & 1:
				res = self.merge(res, self.data[l])
				l += 1
			if r & 1:
				res = self.merge(res, self.data[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.data[l][0] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.data[r - 1][0] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		res = -1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			res = pos - self.num
		if Rmin != -1:
			pos = Rmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			if res == -1:
				res = pos - self.num
			else:
				res = min(res, pos - self.num)
		return res
import sys
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(1):
	n = int(input())
	n *= 9
	spe = n % 10000
	s = str(n)
	s = '000' + s
	L = len(s)
	dp = [[[10 ** 17 for a_b in range(-600, 601)] for i in range(len(s) + 1)] for x in range(2)]
	for i in range(-9, 10):
		for j in range(-9, 10):
			for k in range(-9, 10):
				for l in range(-9, 10):
					for x in range(2):
						tmp_2 = 10 ** 4 * x + 10 ** 3 * i + 10 ** 2 * j + 10 ** 1 * k + l
						a_b = tmp_2 - (spe + i + j + k + l)
						if -470 <= a_b <= 470:
							dp[x][3][a_b] = min(dp[x][3][a_b], 3 * abs(i) + 2 * abs(j) + abs(k))
	for i in range(4, L):
		g = int(s[L - 1 - i])
		for x in range(2):
			for a_b in range(-500, 500):
				for d in range(-9, 10):
					tmp = 10 * x + d
					if tmp == g:
						dp[x][i][a_b] = min(dp[x][i][a_b], dp[0][i - 1][a_b + d] + i * abs(d))
					elif tmp == g + 1:
						dp[x][i][a_b] = min(dp[x][i][a_b], dp[1][i - 1][a_b + d] + i * abs(d))
	print(dp[0][L - 1][0])


def divisao(n):
	if n == 0:
		return 0
	valor = 1
	count = 1
	while 10 * valor + 1 <= n:
		valor *= 10
		valor += 1
		count += 1
	if n <= 5 * valor:
		return divisao(n - valor) + count
	if n > 6 * valor:
		return divisao(10 * valor + 1 - n) + count + 1
	ans1 = divisao(n - valor) + count
	ans2 = divisao(10 * valor + 1 - n) + count + 1
	return min(ans1, ans2)
n = int(input())
print(divisao(n))


import os
import sys
from io import BytesIO, IOBase

def func(n):
	if n < 0:
		raise Exception('Wrong')
	if n <= 6:
		return n
	length = len(str(n))
	big1 = int('1' * length)
	if n <= big1:
		return length + func(big1 - n)
	big5 = int('5' * length)
	big6 = int('6' * length)
	if n <= big5:
		return n // big1 * length + func(n % big1)
	else:
		big11 = int('1' * (length + 1))
		if n >= big6:
			factor = (big11 - n) // big1
			return length + 1 + factor * length + func(big11 - factor * big1 - n)
		return min(5 * length + func(n - big5), 5 * length + 1 + func(big11 - 4 * big1 - n))

def main():
	n = int(parse_input())
	print(func(n))
parse_input = lambda : sys.stdin.readline().rstrip('\r\n')
main()