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;
class MiniOnes
{
  private:
  string digits;
  bool mask = true;
  int n, limu, limc;
  int finallimu, finallimc;
  vector<vector<vector<int>>> table = {};
  void dp();

  public:
  int solution();
  MiniOnes(const string &number)
  {
    digits = "0" + number;
    n = digits.length();
    limu = 6 * n;
    limc = (limu + 9) * 10;
    table.resize(2, vector<vector<int>>(2 * limc + 5, vector<int>(2 * limu + 5, 1e9)));
    table[mask][limc] = vector<int>(2 * limu + 5, 0);
  }
  ~MiniOnes();
};
MiniOnes::~MiniOnes() = default;
void MiniOnes::dp()
{
  int _limu, _limc, _lastlimu, _lastlimc;
  _limu = _lastlimu = limu;
  _limc = _lastlimc = limc;
  for (int p = 0; p < n; p++)
  {
    mask = !mask;
    _lastlimu = _limu;
    _lastlimc = _limc;
    _limu = 6 * (n - p - 1);
    _limc = _limu + 9;
    for (int c = -_limc; c <= _limc; c++)
    {
      for (int u = -_limu; u <= _limu; u++)
      {
        int &res = table[mask][c + limc][u + limu] = 1e9;
        int nextc = 10 * c + digits[n - p - 1] - '0' - u;
        for (int x = -6; x <= 6; x++)
        {
          if (abs(u + x) <= _lastlimu && abs(nextc - x) <= _lastlimc)
            res = min(res, table[!mask][nextc - x + limc][u + x + limu] + (p + 1) * abs(x));
        }
      }
    }
  }
  finallimc = _limc, finallimu = _limu;
}
int MiniOnes::solution()
{
  dp();
  return table[mask][limc][limu];
}
int main()
{
  string number;
  cin >> number;
  MiniOnes a(number);
  cout << a.solution() << endl;
}