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;
using ll = long long;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

void solve(int TestCase) {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    s.push_back('0');

    int n = s.size();
    int max_cnt = 5 * n + 1;
    int max_carry = 5 * n / 9 + 1;
    auto dp = vvvi(max_carry * 2 + 1, vvi(max_cnt, vi(max_cnt, INT_MAX)));
    for(auto i = 0; i < max_cnt; ++i) for(auto j = 0; j < max_cnt; ++j)
        dp[max_carry][i][j] = 0;
    for(auto i = 0; i < n; ++i) {
        auto ndp = vvvi(max_carry * 2 + 1, vvi(max_cnt, vi(max_cnt, INT_MAX)));

        for(auto carry = 0; carry < dp.size(); ++carry) {
            for(auto j = max_cnt - 1; j >= 0; --j) for(auto k = max_cnt - 1; k >= 0; --k) {
                if(dp[carry][j][k] == INT_MAX) continue;

                int rcarry = carry - max_carry;
                int val = rcarry + j - k;
                int d = (val % 10 + 10) % 10;
                int ncarry = val / 10 + max_carry;

                if(s[i] - '0' != d) continue;
                
                if (val < 0 && d != 0) --ncarry;
                ndp[ncarry][j][k] = min(ndp[ncarry][j][k], dp[carry][j][k] + j + k);
            }
        }

        for(auto carry = 0; carry < dp.size(); ++carry) {
            for(auto j = max_cnt - 1; j >= 0; --j) for(auto k = max_cnt - 1; k >= 0; --k) {
                if(k+1 < max_cnt)
                    ndp[carry][j][k] = min(ndp[carry][j][k], ndp[carry][j][k+1]);
                if(j+1 < max_cnt)
                    ndp[carry][j][k] = min(ndp[carry][j][k], ndp[carry][j+1][k]);
                
            }
        }

        swap(dp, ndp);
    }

    auto ret = dp[max_carry][0][0];
    cout << ret << endl;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    //cin >> t;
    for(auto i = 1; i <= t; ++i) {
        //cout << "Case #"<< i << ": ";
        solve(i);
    }
}