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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define filll(a, x) memset(a, x, sizeof(a))
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, INF = 0x7f7f7f7f;
int n, mx, my, f[N][N][N * 10][2]; char s[N];
inline int dfs(int p, int y, int x, int z){
	if(p == n) return y ? INF : 0; if(y > my || y < -my || x > mx || x < -mx) return INF; int ans = f[p][y + my][x + mx][z == 1];
	if(ans == -1) ans = min(dfs(p, y, x + z, z) + n - p, min(dfs(p + 1, y * 10 + s[p + 1] - x, x, 1), dfs(p + 1, y * 10 + s[p + 1] - x, x, -1)));
	return f[p][y + my][x + mx][z == 1] = ans;
}
inline void mian(){
	scanf("%s", s + 2); n = strlen(s + 2) + 1; mx = n * 5, my = mx / 10 + 1;
	rep(i, 2, n) s[i] ^= 48; filll(f, -1); printf("%d\n", dfs(0, 0, 0, 1));
}
int main(){ int qwq = 1; while(qwq--) mian(); return 0; }