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 rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 505
using namespace std;
int f[52][95][905][2],n,mx=450,cc=45;
char s[N];
int calc(int x,int cur,int res,int op){
	if(x==n+1&&!cur)return 0;
	if(abs(cur)>cc||abs(res)>mx||x==n+1)return 0x3f3f3f3f;
	if(~f[x][cur+cc][res+mx][op==1])return f[x][cur+cc][res+mx][op==1];
	f[x][cur+cc][res+mx][op==1]=min(calc(x,cur,res+op,op)+n-x+1,min(calc(x+1,cur*10+s[x+1]-'0'-res,res,1),calc(x+1,cur*10+s[x+1]-'0'-res,res,-1)));
	return f[x][cur+cc][res+mx][op==1];
}
int main(){
	scanf("%s",s+2);n=strlen(s+2);s[1]='0';
	memset(f,~0,sizeof(f));
	printf("%d\n",calc(0,0,0,1));
	return 0;
} 
/*
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 505
using namespace std;
int f[52][95][905][2],n,mx=450,cc=45;
char s[N];
int calc(int x,int cur,int res,int op){
	if(x==n+1&&!cur)return 0;
	if(abs(cur)>cc||abs(res)>mx||x==n+1)return 0x3f3f3f3f;
	if(~f[x][cur+cc][res+mx][op==1])return f[x][cur+cc][res+mx][op==1];
	f[x][cur+cc][res+mx][op==1]=min(calc(x,cur,res+op,op)+n-x+1,min(calc(x+1,cur*10+s[x+1]-'0'-res,res,1),calc(x+1,cur*10+s[x+1]-'0'-res,res,-1)));
	return f[x][cur+cc][res+mx][op==1];
}
int main(){
	scanf("%s",s+2);n=strlen(s+2);s[1]='0';
	memset(f,~0,sizeof(f));
	printf("%d\n",calc(0,0,0,1));
	return 0;
} 
*/