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:
/// You just can't beat the person who never gives up
/// ICPC next year

#include<bits/stdc++.h>
using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}

const int N = 2e5+5 ;
const int base = 11 ;
typedef unsigned long long ull ;

int mod[2] ;
bool is_prime(int x){
    for(int i=2;i*i<=x;++i) if(x%i==0) return 0;
    return 1;
}
int nxt_prime(int x){
    for(int i=x;1;++i) if(is_prime(i)) return i;
}
void get_mods(){
    mod[0] = nxt_prime(rand(9e8,1e9+9)) ;
    mod[1] = nxt_prime(rand(9e8,1e9+9)) ;
    while(mod[1]==mod[0]) mod[1] = nxt_prime(rand(9e8,1e9+9)) ;
}
ull h4(string&n){
    int a = 0 ,b = 0 ;
    for(char i:n){
        a = (a*10ll + i-'0')%mod[0] ;
        b = (b*10ll + i-'0')%mod[1] ;
    }
    return (ull)a * 1e10 + b ;
}
string dif(string a,string b){
    string ret = "";
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int carry = 0;
    for(int i=0;i<b.size();++i){
        int sub = a[i] - b[i] - carry ;
        if(sub<0) sub += 10 ,carry = 1 ;
        else carry = 0 ;
        ret.push_back(sub + '0');
    }
    for(int i=b.size();i<a.size();++i) {
        int sub = a[i] - '0' - carry ;
        if(sub<0) sub += 10 ,carry = 1 ;
        else carry = 0;
        ret.push_back(sub + '0');
    }
    while(ret.size() && ret.back()=='0') ret.pop_back() ;
    if(ret.size()==0) ret += '0' ;
    reverse(ret.begin(), ret.end());
    return ret;
}
string gt[55] ;
string n ;
unordered_map<ull,int> dis ;
int dijkstra(){
    priority_queue<pair<int,string>> pq ;
    pq.push({0,n});
    dis[h4(n)] = 0 ;
    dis[0] = 1e9+5 ;
    while(1){
        string cur = pq.top().second ;
        int d = -pq.top().first ;
        if(cur.size()==1 && cur=="0") return dis[0] ;
        pq.pop() ;
        if(d != dis[h4(cur)]) continue ;
        if(cur.size()==1 && cur[0]=='1'){
            if(dis[0]>d+1){
                dis[0] = d+1 ;
                pq.push({-d-1,"0"});
            }
            continue ;
        }
        string a = gt[cur.size()] ;
        if(a<=cur) a += '1' ;
        string b = a ;
        b.pop_back();
        string toa = dif(a,cur) ;
        string tob = dif(cur,b) ;
        int da = d + a.size() ,db = d + b.size() ;
        ull h4a = h4(toa) ,h4b = h4(tob) ;
        if(!dis.count(h4a)) dis[h4a] = 1e9+5 ;
        if(!dis.count(h4b)) dis[h4b] = 1e9+5 ;
        if(dis[h4a]>da){
            dis[h4a] = da ;
            pq.push({-da,toa});
        }
        if(dis[h4b]>db){
            dis[h4b] = db ;
            pq.push({-db,tob});
        }
    }
    return dis[0];
}
int main(){
    get_mods();
    gt[1] = "1" ;
    for(int i=2;i<55;++i) gt[i] = gt[i-1] + '1' ;
    cin >> n ;
    cout << dijkstra();
    return 0;
}