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<bits/stdc++.h>
#define LL long long 
#define fi first
#define se second
#define mp make_pair
#define PLL pair<LL, LL>
#define PIL pair<int, LL>
#define PII pair<int, int>

using namespace std;

const int N = 251;
const int M = 28;

const int inf = 0x3f3f3f3f;

int n;
char s[N];

int dp[2][2 * M + 1][N][N];


void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	reverse(s + 1, s + 1 + n);
	s[++n] = '0';
	memset(dp, inf, sizeof(dp));
	int cur = 0, pre = 1;
	dp[cur][M][N - 1][N - 1] = 0;
	for (int i = 1; i <= n; i++) {
		swap(cur, pre);
		for (int j = 0; j <= 2 * M; j++) {
			for (int a = 0; a < N; a++) {
				for (int b = 0; b < N; b++) {
					dp[cur][j][a][b] = inf;
				}
			}
		}
		for (int j = 0; j <= 2 * M; j++) {
			for (int a = N - 1; a >= 0; a--) {
				for (int b = N - 1; b >= 0; b--) {
					if (dp[pre][j][a][b] == inf) continue;
					// printf("%d %d %d %d: %d\n", i, j, a, b, dp[pre][j][a][b]);
					if (a > 0) dp[pre][j][a - 1][b] = min(dp[pre][j][a - 1][b],  dp[pre][j][a][b]);
					if (b > 0) dp[pre][j][a][b - 1] = min(dp[pre][j][a][b - 1], dp[pre][j][a][b]);
					int rj = j - M;
					int value = rj + a - b;
					int pos_value = (value % 10 + 10) % 10;
					int next_rj = value < 0 ? ((value + 1) / 10 - 1) : value / 10;
					if (pos_value == s[i] - '0') {
						dp[cur][next_rj + M][a][b] = min(dp[cur][next_rj + M][a][b], dp[pre][j][a][b] + a + b);
					}
				}
			}
		}

	}

	int ans = inf;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans = min(ans, dp[cur][M][i][j]);
		}
	}
	printf("%d\n", ans);
}

int main() {
	int NT = 1;
	while(NT--) solve();
	return 0;
}