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>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef tree<int,null_type,less<int >,rb_tree_tag,tree_order_statistics_node_update>indexed_set;
template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);
template <class T1, class T2>
ostream &operator <<(ostream &os, map<T1,T2>&v);
#ifdef APURBA
#define HERE cout<<"here - "<<__LINE__<<"\n";
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it)
{
    cout<<endl;
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cout << *it << " = " << a << " ";
    err(++it, args...);
}
#else
#define HERE
#define debug(args...)
#endif
const int N = 1e5 +5;
const ll mod = 1e9+7;
typedef pair<int,int> pii;

// Returns true if str1 is smaller than str2,
// else false.
bool isSmaller(string str1, string str2)
{
    int n1 = str1.length(), n2 = str2.length();

    if (n1 < n2)
        return true;
    if (n2 < n1)
        return false;

    for (int i = 0; i < n1; i++)
    {
        if (str1[i] < str2[i])
            return true;
        else if (str1[i] > str2[i])
            return false;
    }
    return false;
}

string findDiff(string str1, string str2)
{
    if (isSmaller(str1, str2))
        swap(str1, str2);

    string str = "";

    int n1 = str1.length(), n2 = str2.length();
    int diff = n1 - n2;

    int carry = 0;

    for (int i = n2 - 1; i >= 0; i--)
    {
        int sub = ((str1[i + diff] - '0') - (str2[i] - '0')
                   - carry);
        if (sub < 0)
        {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;

        str.push_back(sub + '0');
    }

    for (int i = n1 - n2 - 1; i >= 0; i--)
    {
        if (str1[i] == '0' && carry)
        {
            str.push_back('9');
            continue;
        }
        int sub = ((str1[i] - '0') - carry);
        if (i > 0 || sub > 0)
            str.push_back(sub + '0');
        carry = 0;
    }
    while(str.size() && str.back()=='0')
    {
        str.pop_back();
    }
    reverse(str.begin(), str.end());
    return str;
}

string s;
vector<string>vals(55);


void TEST_CASES(int cas)
{
    vals[1] ="1";
    for(int i=2; i<vals.size(); i++)
    {
        vals[i] = vals[i-1] + "1";
    }
    cin>>s;
    priority_queue<pair<int, string> >pq;
    pq.push({0,s});
    unordered_map<string, int>dist;
    dist[s] = 0;
    unordered_map<string, bool>vis;
    while(!pq.empty())
    {
        string a = pq.top().second;
        debug(a,dist[a]);
        if(a.size()==0)
        {
            cout<<dist[a]<<"\n";
            return;
        }
        pq.pop();
        if (vis.count(a))
            continue;
        vis[a] = true;
        vector<int>jabo;
        int sz = a.size();
        if(vals[sz]==a)
        {
            jabo.push_back(sz);
        }
        else if(isSmaller(vals[sz], a) == 1)
        {
            jabo.push_back(sz);
            jabo.push_back(sz+1);
        }
        else
        {
            if(sz-1!=0)
                jabo.push_back(sz-1);
            jabo.push_back(sz);
        }
        for(int i:jabo)
        {
            string bad = findDiff(a , vals[i]);
            if(!dist.count(bad) || dist[bad] > dist[a]+i)
            {
                dist[bad] = dist[a]+i;
                pq.push({-dist[bad],bad});
            }
        }
    }

}




/*


*/

int32_t main()
{
#ifndef APURBA
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    //freopen("input.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    int t=1,cas=0;
    //cin>>t;
    while(t--)
    {
        TEST_CASES(++cas);
    }
    return 0;
}



template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}
template <class T1, class T2>
ostream &operator <<(ostream &os, map<T1,T2>&v)
{
    for(auto i:v)
    {
        os<<"Key : "<<i.first<<" , Value : "<<i.second<<endl;
    }
    return os;
}