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 ;

const int N = 2e5+5 ;

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 n ,gt[55] ;
unordered_map<string,int> dis ;
int dijkstra(){
    priority_queue<pair<int,string>> pq ;
    pq.push({0,n});
    dis[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[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() ;
        if(!dis.count(toa)) dis[toa] = 1e9+5 ;
        if(!dis.count(tob)) dis[tob] = 1e9+5 ;
        if(dis[toa]>da){
            dis[toa] = da ;
            pq.push({-da,toa});
        }
        if(dis[tob]>db){
            dis[tob] = db ;
            pq.push({-db,tob});
        }
    }
    return dis[0];
}
int main(){
    gt[1] = "1" ;
    for(int i=2;i<55;++i) gt[i] = gt[i-1] + '1' ;
    cin >> n ;
    cout << dijkstra();
    return 0;
}