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 JAVA):

Solution:
import java.util.*;
import java.io.*;
public class Edu104F{
	public static void main(String[] main) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		PrintWriter out = new PrintWriter(System.out);
		String s = st.nextToken();
		int[] num = new int[s.length()+1];
		num[1] = s.charAt(0) - 48;
		for(int i = 2; i <= s.length(); i++) {
			num[i] = s.charAt(i-1) - s.charAt(i-2);
		}
		int iters = 0;
		boolean edit = true;
		int min = 10000;
		while(edit) {
			iters++;
			edit = false;
			for(int i = 1; i < s.length(); i++) {
				if(num[i] > 5) {
					num[i-1]++;
					num[i] = num[i]-10;
					num[s.length()]--;
					edit = true;
				}
				else if(num[i] == 5 && num[i-1] < 0) {
					num[i-1]++;
					num[i] = num[i]-10;
					num[s.length()]--;
					edit = true;
				}
				else if(i >= 2 && num[i] == 5 && num[i-1] == 4 && num[i-2] < 0 && (num[s.length()] > 0 || num[s.length()] <= -4)) {
					num[i-2]++;
					num[i-1] = -5;
					num[i] = -5;
					num[s.length()]-=2;
					edit = true;
				}
				else if(i >= 2 && num[i] == 5 && num[i-1] == 4 && num[i-2] < 0 && num[s.length()] < -3 && num[s.length() - 1] > 0) {
					num[i-2]++;
					num[i-1] = -5;
					num[i] = -5;
					num[s.length()]-=2;
					edit = true;
				}
				else if(num[i] == 5 && num[i-1] == 5 && num[s.length()] > 1) {
					num[i-2]++;
					num[i-1] = -4;
					num[i] = -5;
					num[s.length()]-=2;
					edit = true;
				}
				else if(num[i] == 5 && num[i-1] == 5 && num[i-2] == 5) {
					num[i-2]++;
					num[i-1] = -4;
					num[i] = -5;
					num[s.length()]-=2;
					edit = true;
				}
				else if(num[i] < -5) {
					num[i-1]--;
					num[i] = num[i]+10;
					num[s.length()]++;
					edit = true;
				}
				else if(num[i] == -5 && num[i-1] > 0) {
					num[i-1]--;
					num[i] = num[i]+10;
					num[s.length()]++;
					edit = true;
				}
				else if(i >= 2 && num[i] == -5 && num[i-1] == -4 && (num[i-2] > 0) && (num[s.length()] < 0 || num[s.length()] >= 4)) {
					num[i-2]--;
					num[i-1] = 5;
					num[i] = 5;
					num[s.length()]+=2;
					edit = true;
				}
				else if(i >= 2 && num[i] == -5 && num[i-1] == -4 && (num[i-2] == -4 && num[i-3] > 0) && (num[s.length()] < 0 || num[s.length()] >= 4)) {
					num[i-2]--;
					num[i-1] = 5;
					num[i] = 5;
					num[s.length()]+=2;
					edit = true;
				}
				else if(i >= 2 && num[i] == -5 && num[i-1] == -4 && num[i-2] > 0 && num[s.length()] > 3 && num[s.length() - 1] < 0) {
					num[i-2]--;
					num[i-1] = 5;
					num[i] = 5;
					num[s.length()]+=2;
					edit = true;
				}
				else if(num[i] == -5 && num[i-1] == -5 && num[s.length()] < -1) {
					num[i-2]--;
					num[i-1] = 4;
					num[i] = 5;
					num[s.length()]+=2;
					edit = true;
				}
				else if(num[i] == -5 && num[i-1] == -5 && num[i-2] == -5) {
					num[i-2]--;
					num[i-1] = 4;
					num[i] = 5;
					num[s.length()]+=2;
					edit = true;
				}
			}
			if(num[s.length()] > 6) {
				num[s.length()-1]++;
				num[s.length()] -= 11;
				edit = true;
			}
			else if(num[s.length()] >= 5 && num[s.length() - 1] < 0) {
				num[s.length()-1]++;
				num[s.length()] -= 11;
				edit = true;
			}
			else if(s.length() >= 2 && num[s.length()] == 6 && num[s.length()-1] == 4 && num[s.length()-2] < 0) {
				num[s.length()-1]++;
				num[s.length()] -= 11;
				edit = true;
			}
			else if(num[s.length()] < -6) {
				num[s.length()-1]--;
				num[s.length()] += 11;
				edit = true;
			}
			else if(num[s.length()] <= -5 && num[s.length() - 1] > 0) {
				num[s.length()-1]--;
				num[s.length()] += 11;
				edit = true;
			}
			else if(s.length() >= 2 && num[s.length()] == -6 && num[s.length()-1] == -4 && num[s.length()-2] > 0) {
				num[s.length()-1]--;
				num[s.length()] += 11;
				edit = true;
			}
			int ans = 0;
			for(int i = 0; i <= s.length(); i++) {
				//out.print(num[i] + " ");
				ans += (s.length() + 1 - i)*Math.abs(num[i]);
			}
			min = Math.min(ans, min);
			if(iters > 7000000) {
				break;
			}
		}
		int ans = 0;
		for(int i = 0; i <= s.length(); i++) {
			//out.print(num[i] + " ");
			ans += (s.length() + 1 - i)*Math.abs(num[i]);
		}
		out.println(Math.min(min,ans));
		out.close();
	}
}