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>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define __unique(V) (V).resize(unique((V).begin(),(V).end())-(V).begin())
#define cntbit(X)   __builtin_popcount((X))
#define bit(S,i) (((S)>>(i))&1)
#define PI	acos(-1)
#define fi  first
#define se  second
#define LL  long long
#define ii  pair<int,int>
#define iii pair<int,ii>
#define eb  emplace_back
#define TASK "1487F"
using namespace std;
const int mov = 28;
const int oo = 1e6;
string s;
int n;
int dp[2][57][251][251];
deque <int> digit;
///--------------------------
void    readf(){
    cin >> s;
    for(char c : s) digit.push_front(c - '0');
    digit.eb(0);
}
///--------------------------
void    solve(){
    for(int i = digit.size(); i >= 0; --i)
    for(int car = -28; car <= 28; ++car)
    for(int sp = 0; sp <= 250; ++sp)
    for(int sn = 0; sn <= 250; ++sn){
        bool t = i & 1;
        if (i == digit.size()){
            dp[t][mov + car][sp][sn] = (car == 0 ? 0 : oo);
            continue;
        }
        int &rs = dp[t][mov + car][sp][sn];
        rs = oo;
        if (sp > 0) rs = min(rs,dp[t][mov + car][sp - 1][sn]);
        if (sn > 0) rs = min(rs,dp[t][mov + car][sp][sn - 1]);
        if (((sp - sn + car) % 10 + 10) % 10 == digit[i]) {
            int _car = car + sp - sn;
            if (_car < 0) _car = (_car - 9) / 10;
            else _car = _car / 10;
            assert(-28 <= _car && _car <= 28);
            rs = min(rs,dp[t ^ 1][mov + _car][sp][sn] + sp + sn);
        }
    }
    cout << dp[0][mov + 0][250][250] << '\n';
}
///--------------------------
int     main(){
	srand(time(NULL));
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    #ifdef TLH2203
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    #endif // TLH2203
    readf();
    solve();
}