題干：

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.

題目大意：

? ? 給一個n，找兩個數a,b，使得在滿足a+b=n的前提下，a和b的各位數的和最大。

解題報告：

? ? ?這題有點小坑啊，但是這么想啊，肯定是9越多越好，所以先找出最多的9999之類的，剩下的再隨便挑。（因為不難想到，肯定沒有比這個的和? 更大的了）所以就這么構造就行，反正是SJ題。

? ?給一個錯誤的想法，up=1，然后每次都*10+9，找到最大的滿足的，這樣就大錯特錯了。對于123這個樣例，輸出為15,但正確答案為24（99+24)。所以啊要先湊9，因為可以證明其他的任何最大組合，都可以由這個a來借給b。

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std;int main() {ll n,a,b;cin>>n;ll up=1;while(n>=up) {up=up*10;}up/=10;up--; // cout<<up<<endl;a=up;b=n-up;ll sum=0;while(a) {sum+=a%10;a/=10;}while(b) {sum+=b%10;b/=10;}printf("%d\n",sum);return 0; }

其實寫成更賞心悅目，思路清晰。

while(1){temp1*=10;if(temp1*10>=n)break;}temp1--;

?

總結

以上是生活随笔為你收集整理的【 CodeForces - 1060B 】Maximum Sum of Digits（思维，构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。