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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
using namespace std;
#define ll long long
#define ri register int

const int N = 251;
const int M = 28;

string s;
int n;
int dp[2][M*3][N+10][N+10];

signed main() {
    cin >> s;
    reverse(s.begin(),s.end());
    s += "0";
    n = s.size();
    memset(dp[0],0x3f,sizeof dp[0]);
    dp[0][M][N-1][N-1] = 0;
    
    for (int i = 0;i < n;++i) {
        memset(dp[1],0x3f,sizeof dp[1]);
        for (int j = 0;j < M*2+1;++j) {
            for (int up = N-1;up >= 0;--up) {
                for (int down = N-1;down >= 0;--down) {
                    if (dp[0][j][up][down] != 0x3f3f3f3f) {
                        if (up > 0) dp[0][j][up-1][down] = min(dp[0][j][up-1][down],dp[0][j][up][down]);
                        if (down > 0) dp[0][j][up][down-1] = min(dp[0][j][up][down-1],dp[0][j][up][down]);
                        int now = j - M;
                        int dig = (now + up - down) % 10;
                        if (dig < 0) dig += 10;
                        int tim = (now + up - down) / 10;
                        if ((now + up - down) < 0 && dig != 0) --tim;
                        if (dig == s[i] - '0') {
                            dp[1][tim+M][up][down] = min(dp[1][tim+M][up][down],dp[0][j][up][down] + up + down);
                        }
                    }
                }
            }
        }
        swap(dp[0],dp[1]);
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0;i < N;++i) {
        for (int j = 0;j < N;++j) {
            ans = min(ans,dp[0][M][i][j]);
        }
    }
    printf("%d",ans);
}