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=1e9;
char s[55];
int n,dp[52][505][1205][2];
int dfs(int w,int val,int dt,int fh){
	if(w>n)return val?inf:0;
	if(val+250<0||val+250>502||dt+600<0||dt+600>1201)return inf;
	int&F=dp[w][val+50][dt+500][fh==1];
	if(F!=-1)return F;
	F=dfs(w,val,dt-fh,fh)+n-w+1;
	F=min(F,dfs(w+1,val*10+s[w+1]-dt*10,dt,1));
	F=min(F,dfs(w+1,val*10+s[w+1]-dt*10,dt,-1));
	return F;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i)s[i]-='0';
	memset(dp,-1,sizeof dp);
	cout<<dfs(0,0,0,-1)<<'\n';
	return 0;
}