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

Solution:
#include <stdio.h>
#include <string.h>

#define N	52
#define K	(N * 6)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

void carry(int *aa, int n) {
	int i;

	for (i = 0; i < n; i++)
		if (aa[i] >= 10)
			aa[i + 1] += aa[i] / 10, aa[i] %= 10;
		else if (aa[i] < 0)
			aa[i + 1] -= (-aa[i] + 9) / 10, aa[i] = (aa[i] % 10 + 10) % 10;
}

int main() {
	static char aa[N + 1];
	static int bb[N + 1], dp[K * 2 + 1], dq[K * 2 + 1], dp_[K * 2 + 1], dq_[K * 2 + 1];
	int n, i, j, k, ans;
	char tmp;

	scanf("%s", aa), n = strlen(aa);
	for (i = 0; i < n; i++)
		aa[i] -= '0';
	for (i = 0, j = n - 1; i < j; i++, j--)
		tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
	n += 2;
	memset(dp, 0x3f, (K * 2 + 1) * sizeof *dp), memset(dq, 0x3f, (K * 2 + 1) * sizeof *dq); 
	dp[K] = 0;
	for (i = n - 2; i >= 0; i--) {
		memset(dp_, 0x3f, (K * 2 + 1) * sizeof *dp_), memset(dq_, 0x3f, (K * 2 + 1) * sizeof *dq_); 
		for (k = 0; k <= K * 2; k++) {
			int x;

			for (j = 0; j <= i + 1; j++)
				bb[j] = aa[j] + k - K;
			carry(bb, i + 2), bb[i + 2] = 0;
			if ((x = dp[k]) != INF) {
				int d = bb[i + 1] == 1 ? 10 : bb[i];

				for (j = i; j >= 0; j--)
					bb[j] -= d;
				carry(bb, i + 2);
				if (bb[i + 2] < 0)
					d--;
				if (d < 10) {
					dp_[k - d] = min(dp_[k - d], x + d * (i + 1));
					if (++d < 10)
						dq_[k - d] = min(dq_[k - d], x + d * (i + 1));
				}
			}
			for (j = 0; j <= i + 1; j++)
				bb[j] = -bb[j];
			carry(bb, i + 2), bb[i + 2] = 0;
			if ((x = dq[k]) != INF) {
				int d = bb[i + 1] == 1 ? 10 : bb[i];

				for (j = i; j >= 0; j--)
					bb[j] -= d;
				bb[0]--;
				carry(bb, i + 2);
				if (bb[i + 2] < 0)
					d--;
				if (d < 10) {
					dq_[k + d] = min(dq_[k + d], x + d * (i + 1));
					if (++d < 10)
						dp_[k + d] = min(dp_[k + d], x + d * (i + 1));
				}
			}
		}
		memcpy(dp, dp_, (K * 2 + 1) * sizeof *dp_), memcpy(dq, dq_, (K * 2 + 1) * sizeof *dq_); 
	}
	ans = INF;
	for (k = 0; k <= K * 2; k++)
		if ((aa[0] + k - K) % 10 == 0)
			ans = min(ans, dp[k]);
	printf("%d\n", ans);
	return 0;
}