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>
using namespace std;

const int maxn = 60;
const int A = 250;
const int B = 250;
const int inf = 2147483647;

int dp[maxn][A*2+5][B*2+5];
char s[maxn];
void mii(int &u,int v){
	u=min(u,v);
}
int main(){
	scanf("%s",s+5);
	for(int i=1;i<=4;++i)s[i]='0';
	int n=strlen(s+1);
	memset(dp,0x3f,sizeof(dp));
	dp[0][A][B]=0;
	for(int i=0;i<n;++i){
		for(int j=-A;j<=A;++j){
			for(int k=-B;k<=B;++k){
				for(int h=-6;h<=6;++h){
					int nk=k+h;
					int nj=j*10+s[i+1]-'0'-nk;
					if(abs(nk)>B || abs(nj)>A)continue;
					mii(dp[i+1][nj+A][nk+B],dp[i][j+A][k+B]+abs(h)*(n-i));
//					if(abs(nj)<=10 && abs(nk)<=10)printf("%d,%d,%d,%d  %d,%d,%d\n",i+1,nj,nk,dp[i+1][nj+A][nk+B],j,k,dp[i][j+A][k+B]);
				}
			}
		}
	}
	int ans=inf;
	for(int i=-B;i<=B;++i){
		ans=min(ans,dp[n][A][i+B]);
	}
	printf("%d\n",ans);
}