#include <bits/stdc++.h>
using namespace std;
void OUT_TST(string s, istream_iterator<string> it) { cerr << s; }
template <typename T, typename... Args>
void OUT_TST(string s, istream_iterator<string> it, T a, Args... args) {
  cerr << *it << "=" << a << " ";
  OUT_TST(s, ++it, args...);
}
template <class T>
void rd(T &ret) {
  ret = 0;
  bool ok = 0, u = 0;
  for (;;) {
    int c = getchar();
    if (c >= '0' && c <= '9')
      ret = (ret << 3) + (ret << 1) + c - '0', ok = 1;
    else if (c == '-')
      u = 1;
    else if (ok) {
      if (u) ret *= -1;
      return;
    }
  }
}
long long powmod(long long p, long long n, long long mod) {
  long long ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
  }
  return ret;
}
template <class T>
bool chmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool chmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int MX = (int)1e9;
long long n;
int dp[20][2][2][2];
bool ok_end(int first, int p) {
  if (p == 0) return 1;
  return first > 0;
}
int dfs(int p, int jin, int has_f, int has_s, long long base) {
  if (base > n) {
    if (jin == 0 && has_f == 0 && has_s == 0) return 0;
    return -MX;
  }
  int &ans = dp[p][jin][has_f][has_s];
  if (ans != -1) return ans;
  ans = -MX;
  for (int i = (0); i < (10); i++)
    for (int j = (0); j < (10); j++) {
      int t = i + j + jin;
      if ((t % 10) != ((n / base) % 10)) continue;
      if (!has_f && i) continue;
      if (!has_s && j) continue;
      chmax(ans, dfs(p + 1, t >= 10, has_f, has_s, base * 10ll) + i + j);
      if (ok_end(i, p))
        chmax(ans, dfs(p + 1, t >= 10, 0, has_s, base * 10ll) + i + j);
      if (ok_end(j, p))
        chmax(ans, dfs(p + 1, t >= 10, has_f, 0, base * 10ll) + i + j);
      if (ok_end(i, p) && ok_end(j, p))
        chmax(ans, dfs(p + 1, t >= 10, 0, 0, base * 10ll) + i + j);
    }
  return ans;
}
int main() {
  cin >> n;
  memset(dp, -1, sizeof dp);
  cout << dfs(0, 0, 1, 1, 1) << endl;
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

You are given a positive integer n.

Let S(x) be sum of digits in base 10 representation of x, for example, S(123) = 1 + 2 + 3 = 6, S(0) = 0.

Your task is to find two integers a, b, such that 0 ≤ a, b ≤ n, a + b = n and S(a) + S(b) is the largest possible among all such pairs.

Input

The only line of input contains an integer n (1 ≤ n ≤ 10^{12}).

Output

Print largest S(a) + S(b) among all pairs of integers a, b, such that 0 ≤ a, b ≤ n and a + b = n.

Examples

Input

35


Output

17


Input

10000000000


Output

91

Note

In the first example, you can choose, for example, a = 17 and b = 18, so that S(17) + S(18) = 1 + 7 + 1 + 8 = 17. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, a = 5000000001 and b = 4999999999, with S(5000000001) + S(4999999999) = 91. It can be shown that it is impossible to get a larger answer.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void OUT_TST(string s, istream_iterator<string> it) { cerr << s; }
template <typename T, typename... Args>
void OUT_TST(string s, istream_iterator<string> it, T a, Args... args) {
  cerr << *it << "=" << a << " ";
  OUT_TST(s, ++it, args...);
}
template <class T>
void rd(T &ret) {
  ret = 0;
  bool ok = 0, u = 0;
  for (;;) {
    int c = getchar();
    if (c >= '0' && c <= '9')
      ret = (ret << 3) + (ret << 1) + c - '0', ok = 1;
    else if (c == '-')
      u = 1;
    else if (ok) {
      if (u) ret *= -1;
      return;
    }
  }
}
long long powmod(long long p, long long n, long long mod) {
  long long ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
  }
  return ret;
}
template <class T>
bool chmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool chmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int MX = (int)1e9;
long long n;
int dp[20][2][2][2];
bool ok_end(int first, int p) {
  if (p == 0) return 1;
  return first > 0;
}
int dfs(int p, int jin, int has_f, int has_s, long long base) {
  if (base > n) {
    if (jin == 0 && has_f == 0 && has_s == 0) return 0;
    return -MX;
  }
  int &ans = dp[p][jin][has_f][has_s];
  if (ans != -1) return ans;
  ans = -MX;
  for (int i = (0); i < (10); i++)
    for (int j = (0); j < (10); j++) {
      int t = i + j + jin;
      if ((t % 10) != ((n / base) % 10)) continue;
      if (!has_f && i) continue;
      if (!has_s && j) continue;
      chmax(ans, dfs(p + 1, t >= 10, has_f, has_s, base * 10ll) + i + j);
      if (ok_end(i, p))
        chmax(ans, dfs(p + 1, t >= 10, 0, has_s, base * 10ll) + i + j);
      if (ok_end(j, p))
        chmax(ans, dfs(p + 1, t >= 10, has_f, 0, base * 10ll) + i + j);
      if (ok_end(i, p) && ok_end(j, p))
        chmax(ans, dfs(p + 1, t >= 10, 0, 0, base * 10ll) + i + j);
    }
  return ans;
}
int main() {
  cin >> n;
  memset(dp, -1, sizeof dp);
  cout << dfs(0, 0, 1, 1, 1) << endl;
  return 0;
}

```