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 N 250
#define M 30
using namespace std;
int noww , las , dp[2][62][260][260] , ans = 1e9;
string s;
int main()
{
	cin >> s; s = '0' + s;
	memset(dp , 0x7f / 3 , sizeof(dp)); dp[1][M][N][N] = 0;
	for(int i = s.size() - 1 ; i >= 0 ; i-- )
	{
		las = noww; noww ^= 1;
		memset(dp[las] , 0x7f / 3 , sizeof(dp[las]));
		for(int c = 0 ; c <= 2 * M ; c++ )
		{
			for(int cp = N ; cp >= 0 ; cp-- )
			{
				for(int cn = N ; cn >= 0 ; cn-- )
				{
					if(cp) dp[noww][c][cp - 1][cn] = min(dp[noww][c][cp - 1][cn] , dp[noww][c][cp][cn]);
					if(cn) dp[noww][c][cp][cn - 1] = min(dp[noww][c][cp][cn - 1] , dp[noww][c][cp][cn]);
					int val = c + cp - cn - M;
					int cc = val / 10 + M , d = val % 10;
					if(d < 0) d += 10 , cc--;
					if(d == s[i] - '0')
						dp[las][cc][cp][cn] = min(dp[las][cc][cp][cn] , dp[noww][c][cp][cn] + cp + cn);
				}
			}
		}
	}
	for(int cp = N ; cp >= 0 ; cp-- )
		for(int cn = N ; cn >= 0 ; cn-- ) ans = min(ans , dp[las][M][cp][cn]);
	printf("%d" , ans);
	return 0;
}