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 inf=1000000;
int n,a[10000],lim1,lim2,f[60][100][1000][3];
char s[10000];
int dp(int p,int x,int y,int z)
{
	if(p==n) return x?inf:0;
	if(abs(x)>lim2||abs(y)>lim1) return inf;
	if(f[p][x][y][z]>=0) return f[p][x][y][z];
	return f[p][x][y][z]=min(dp(p,x,y+(z<<1)-1,z)+n-p,min(dp(p+1,x*10+a[p+1]-y,y,0),dp(p+1,x*10+a[p+1]-y,y,1)));
}
int main()
{
	scanf("%s",s+2);
	n=strlen(s+2)+1;
	for(int i=2;i<=n;i++) a[i]=s[i]-48;
	lim1=n+(n<<2);
	lim2=lim1/10+1;
	memset(f,-1,sizeof(f));
	printf("%d",dp(0,0,0,1));
}