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;

const int MAX_N = 50 + 5;
const int MAX_M = 400 + 5;
int n;
char str[MAX_N];
int f[2][MAX_N][MAX_M][MAX_M];

bool in_border(int x, int y) {
    x += 200; y += 200;
    return x >= 0 && y >= 0 && x < MAX_M && y < MAX_M;
}

void dfs(int dir, int i, int lazy, int rem) {
    int &F = f[dir < 0][i][lazy + 200][rem + 200];
    if (F >= 0) return ;
    if (i == n) {
        F = rem ? 0x3f3f3f3f : 0;
        return ;
    }
    F = 0x3f3f3f3f;
    const int cur = str[i] - lazy + rem * 10;
    if (in_border(lazy, cur)) {
        dfs(1, i + 1, lazy, cur);
        dfs(-1, i + 1, lazy, cur);
        F = min(f[0][i + 1][lazy + 200][cur + 200], f[1][i + 1][lazy + 200][cur + 200]);
    }
    if (in_border(lazy + dir, rem)) {
        dfs(dir, i, lazy + dir, rem);
        F = min(F, f[dir < 0][i][lazy + dir + 200][rem + 200] + n - i);
    }
}

int main() {
    scanf("%s", str + 1);
    str[0] = 48;
    n = strlen(str);
    for (int i = 0; i < n; i ++) str[i] ^= 48;
    memset(f, -1, sizeof(f));
    dfs(1, 0, 0, 0);
    printf("%d\n", f[0][0][200][200]);
    return 0;
}