Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.

Input

The first line of the input contains integer n (1 ≤ n < 1015).

Output

Print expected minimal number of digits 1.

A dfs type of recursion .nice one

#include<bits/stdc++.h>

using namespace std;

#define ll long long int 

ll pow11[20];

int countdig(ll num)

{

int res=0;

 while(num!=0)

 {

  num=num/10;

  res++;

 }

 return res;

}

int cntst=0;

ll ans=100000000;

void solve(ll num,int steps)

{

       if(steps>ans)

       return ;

   //    cout<<num<<endl;

       if(num==0)

       {

           ans=steps;

           return ;

}

 ll val=1;

 int temp=1;

 while(val*10+1<=num)

 {

    val=val*10+1;

    temp++;

}

ll v2=val*10+1;

// cout<<"val "<<val<<" "<<v2<<endl;

 solve(num%val,steps+temp*(num/val));

 solve(v2-num,steps+temp+1);       

  

}

void pre()

{

  pow11[1]=1;

 for(int i=2;i<=16;i++)

 {

   pow11[i]=10*pow11[i-1]+1;

 }

 

}

int main()

{

  ll n;

  pre();

  cin>>n;

  solve(n,0);

  cout<<ans<<endl;

}