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,hf=30,inf=1e9+10;
int dp[2][maxn*6][maxn*6][65];
string s;
int n;
int main(){
	cin>>s;
	reverse(s.begin(),s.end());s+='0';s+='0';
	n=(int)s.size();
	for(int i=0;i<n;i++)s[i]-='0';
//	for(int i=0;i<n;i++)cout<<int(s[i])<<" ";cout<<endl; 
	for(int i=0;i<2;i++)for(int s1=0;s1<maxn*5;s1++)for(int s2=0;s2<maxn*5;s2++)
		for(int t=0;t<maxn;t++)dp[i][s1][s2][t]=inf;
	for(int s1=0;s1<maxn*6;s1++)for(int s2=0;s2<maxn*6;s2++){
		if(s1+s2>=maxn*6)continue;
		if((s1%10-s2%10+10)%10==s[0]){
			int t=s1-s2>=0?(s1-s2)/10:((s2-s1)%10==0?(s1-s2)/10:((s1-s2)/10-1));
			if(t+hf<65&&t+hf>=0)dp[0][s1][s2][hf+t]=0;
		}
	}
	for(int i=0;i+1<n;i++){
		int now=i&1,nxt=now^1;
		for(int s1=0;s1<maxn*6;s1++)for(int s2=0;s2<maxn*6;s2++)for(int t=0;t<maxn;t++)
			dp[nxt][s1][s2][t]=inf;
		for(int s1=0;s1<maxn*6;s1++)for(int s2=0;s2<maxn*6;s2++)for(int t=0;t<maxn;t++){
			if(dp[now][s1][s2][t]>=inf||s1+s2>=maxn*6)continue;
			int add=t-hf; 
			for(int ad1=0;ad1<=min(6,s1);ad1++){
				int val=s1-ad1-s2+add;
				if((val+500)%10==s[i+1]){
					int nadd=val>=0?val/10:(abs(val)%10==0?val/10:(val/10-1));
					if(nadd+hf>=65||nadd+hf<0)continue;
					checkmin(dp[nxt][s1-ad1][s2][nadd+hf],dp[now][s1][s2][t]+ad1*(i+1));
				}
			}
			for(int ad2=0;ad2<=6&&ad2<=s2;ad2++){
				int val=s1-s2+ad2+add;
				if((val+500)%10==s[i+1]){
					int nadd=val>=0?val/10:(abs(val)%10==0?val/10:(val/10-1));
					if(nadd+hf>=65||nadd+hf<0)continue;
					checkmin(dp[nxt][s1][s2-ad2][nadd+hf],dp[now][s1][s2][t]+ad2*(i+1));
				}
			}
		}
	}
	cout<<dp[(n-1)&1][0][0][hf]<<endl;
	return 0;
}