【 Maximum Sum of Digits 】【CodeForces - 1060B】（思维）

题目：

You are given a positive integer nn.

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

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

Input

The only line of input contains an integer nn (1≤n≤1012)(1≤n≤1012).

Output

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

Examples

Input

35
      

Output

17
      

Input

10000000000
      

Output

91
      

Note

In the first example, you can choose, for example, a=17a=17 and b=18b=18, so that S(17)+S(18)=1+7+1+8=17S(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=5000000001a=5000000001 and b=4999999999b=4999999999, with S(5000000001)+S(4999999999)=91S(5000000001)+S(4999999999)=91. It can be shown that it is impossible to get a larger answer.

解题报告：刚上来就以为是去找中间值的左右，然后求位之和，但是wa了，因为思路走错了，之后就是想到了，要尽量使小于n的数字中尽可能的多出现9，所以寻找第一个小于n的除第一位之外全是9的数，之后就按位求解。有个坑点，就是小于18的直接 输出就可以，因为小于这个的情况没有办法找19****的存在，会wa掉。

ac代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll cal(ll x)
{
	ll ret=0;
	while(x)
	{
		ret+=(x%10);
		x/=10;
	}
	return ret;
}
int main()
{
	ll n;
	scanf("%lld",&n);
	if(n<=18)
	{
		printf("%lld\n",n);
		return 0;
	}
	int len=0;
	ll xx=n;
	while(xx)
	{
		len++;
		xx/=10; 
	}
	ll ans=0;
	for(int i=1;i<=9;i++)
	{
		ll x=i;
		for(int j=1;j<len;j++)
			x=x*10+9;
		if(x>n)
			x/=10;
		ans=max(ans,cal(x)+cal(n-x));
	}
	printf("%lld\n",ans);
	return 0;
}