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 all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...); cout<<'\n';}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string n;
    cin>>n;
    vector<string> nums(n.size()+2);
    for (int i=1; i<(int)nums.size(); i++) nums[i]=string(i, '1');

    auto sub=[](string a, string b) -> string {
        string res(a.size(), 0);
        reverse(all(a)), reverse(all(b));
        b+=string(a.size()-b.size(), '0');
        bool borrow=0;
        for (int i=0; i<(int)a.size(); i++) {
            int ai=a[i]-borrow;
            int bi=b[i];
            borrow=0;
            if (bi>ai) {
                borrow=true;
                ai+=10;
            }
            res[i]=ai-bi+'0';
        }
        while (res.back()=='0') res.pop_back();
        reverse(all(res));
        return res;
    };

    using pis=pair<int, string>;
    priority_queue<pis, vector<pis>, greater<pis>> pq;
    pq.emplace(0, n);
    unordered_map<string, int> dis;
    dis[n]=0;
    while (!pq.empty()) {
        auto [d, cur] = pq.top();
        pq.pop();
        if (dis[cur]!=d) continue;
        auto num1=nums[cur.size()];
        if (num1==cur) {
            dis[""]=d+cur.size();
            break;
        }
        string num2;
        if (num1>cur) num2=nums[cur.size()-1];
        else {
            num2=num1;
            num1=nums[cur.size()+1];
        }

        string nxt=sub(num1, cur);
        if (!dis.count(nxt) || dis[nxt]>d+sz(num1)) {
            dis[nxt]=d+sz(num1);
            pq.emplace(d+sz(num1), nxt);
        }
        if (!num2.empty()) {
            nxt=sub(cur, num2);
            if (!dis.count(nxt) || dis[nxt]>d+sz(num2)) {
                dis[nxt]=d+sz(num2);
                pq.emplace(d+sz(num2), nxt);
            }
        }
    }
    cout<<dis[""];
    return 0;
}