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:
/*long long or int&the MAX_INT or MIN_INT*/
/*the size of a[]&inline*/
/*xx 396*/
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
template<class T>inline void checkmin(T &a,const T &b){if(b<a)a=b;}
template<class T>inline void checkmax(T &a,const T &b){if(b>a)a=b;}
const int maxn=55,hft=30,inf=1e9+10,hfs=maxn*6;
int dp[2][maxn*12][65];
string str;
int n;
int main(){
	cin>>str;
	reverse(str.begin(),str.end());str+='0';str+='0';
	n=(int)str.size();
	for(int i=0;i<n;i++)str[i]-='0';
//	for(int i=0;i<n;i++)cout<<int(s[i])<<" ";cout<<endl; 
	for(int i=0;i<maxn*12;i++)for(int j=0;j<65;j++)dp[0][i][j]=dp[1][i][j]=inf;
	for(int s=0;s<maxn*12;s++){
		int ns=s-hfs;
		if((ns+500)%10==str[0]){
			int t=ns>=0?ns/10:(abs(ns)%10==0?ns/10:(ns/10-1));
			if(t+hft<65&&t+hft>=0)dp[0][s][hft+t]=0;
		}
	}
	for(int i=0;i+1<n;i++){
		int now=i&1,nxt=now^1;
		for(int s=0;s<maxn*12;s++)for(int t=0;t<maxn;t++)dp[nxt][s][t]=inf;
		for(int j=0;j<maxn*12;j++)for(int t=0;t<maxn;t++){
			if(dp[now][j][t]>=inf)continue;
			int add=t-hft,s=j-maxn*6;
		//	if(s==4&&t==0)cout<<i<<" "<<s<<" "<<t<<" "<<dp[now][j][t]
			for(int ad=0;ad<=6;ad++){
				int val=s-ad+add;
				if((val+500)%10==str[i+1]){
					int nadd=val>=0?val/10:(abs(val)%10==0?val/10:(val/10-1));
					if(nadd+hft>=65||nadd+hft<0)continue;
					checkmin(dp[nxt][s-ad+hfs][nadd+hft],dp[now][j][t]+ad*(i+1));
				}
				val=s+ad+add;
				if((val+500)%10==str[i+1]){
					int nadd=val>=0?val/10:(abs(val)%10==0?val/10:(val/10-1));
					if(nadd+hft>=65||nadd+hft<0)continue;
					checkmin(dp[nxt][s+ad+hfs][nadd+hft],dp[now][j][t]+ad*(i+1));
				}
			}		
		}
	}
	cout<<dp[(n-1)&1][hfs][hft]<<endl;
	return 0;
}