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>
using namespace std;
#define ENDL              "\n"
#define fv                first
#define sv                second
#define ll                long long
#define eb                emplace_back
#define pll               pair <ll,ll>
#define pii               pair <int,int>
#define mp(a,b)           make_pair(a,b)
#define READ(x)           freopen(x,"r",stdin)
#define WRITE(x)          freopen(x,"w",stdout)
#define Add(a,b,m)        (a % m + b % m ) % m
#define Mul(a,b,m)        (a % m * b % m ) % m
#define isWorking()       cout<<"Wroking"<<endl
#define all(x)            (x).begin(),(x).end()
#define allr(x)           (x).rbegin(),(x).rend()
#define PRINT(ok)         cout << (ok? "YES":"NO") << ENDL
#define DoublePrint(x,a)  cout<<fixed<<setprecision(x)<<a<<endl
#define Make_Slow()       ios_base :: sync_with_stdio(0),cin.tie(0),cout.tie(0);
const ll mod = 1e9+7, INFL = 1e18, INFI = 1e9, N = 1e6+5;
int Case = 1, cas = 0;

string A[55];

string Subtract(string a, string b){
    if( ( a.size() < b.size() ) || (a.size() == b.size() && a < b) ) swap(a,b);

    string Ans;
    reverse(all(a));
    reverse(all(b));

    while(b.size() != a.size()) b += "0";
    int Carry = 0;
    for(int i = 0; i < a.size(); i++){
        int Cur = a[i] - b[i] - Carry;
        Carry = 0;
        if(Cur < 0) Cur += 10, Carry = 1;
        Ans.push_back( Cur+'0' );
    }
    while(!Ans.empty() && Ans.back() == '0') Ans.pop_back();
    reverse(all(Ans));
    return Ans;
}

int dijkstra(string n){
    map < string, int> d;
    d[n] = 0;
    priority_queue < pair <int,string> > pq;
    pq.push( mp(0,n) );
    while(!pq.empty()){
        auto tp = pq.top();
        pq.pop();
        int mov = -tp.fv;
        if(tp.sv == "") return mov;
        if(d[tp.sv] < mov ) continue;
        for(int i = 0; i < 2; i++){
            int Cnt = tp.sv.size();
            if(Cnt+i <= 0) continue;
            string nxt = Subtract(tp.sv , A[Cnt+i]);
            int Cost = mov + Cnt + i;
            if(d.find(nxt) == d.end() || d[nxt] > Cost){
                d[nxt] = Cost;
                pq.push( mp(-Cost,nxt) );
            }
        }
    }
}

int main(){
    Make_Slow();

    A[1] = "1";
    for(int i = 2; i < 55; i++) A[i] = A[i-1]+"1";

    string n; cin >> n;
    cout << dijkstra(n) << ENDL;

    return 0;
}