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 <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <iomanip>
#include <numeric>
#include <cmath>
using namespace std;

int main() {
	string s;
	cin >> s;
	unordered_map<int, unordered_map<int, int>> um1, um2;
	um1[0][0] = 0;
	s = "0" + s;
	for (int i = 0; i < s.size(); i++) {
		int d = s[i] - '0';
		int one = s.size() - i;
		um2.clear();
		// cout << "======" << i << "======" << endl;
		for (auto p1 : um1) {
			d = s[i] - '0';
			for (auto p2 : p1.second) {
				int left = p1.first;
				int flip = p2.first;
				int r = p2.second;
				d = s[i] - '0';
				d = d - left - flip;
				
				// cout << left << " " << flip << " " << r << " " << d << endl;
				for (int i = -25; i <= 25; i++) {
					if (um2[i * 10].count(flip + (d + i)) == 0 
						or um2[i * 10][flip + i + d] > r + abs(d + i) * one) {
						um2[i * 10][flip + (d + i)] = r + abs(d + i) * one;
					}
				}
			}
		}
		um1 = um2;
	}
	int res = -1;
	for (auto p1 : um1) {
		if (p1.first != 0) continue;
		for (auto p2 : p1.second) {
			if (res == -1 or res > p2.second) res = p2.second;
		}
	}
	cout << res << endl;
}