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.

Solution (in JAVA):

Solution:
import java.util.*;
	import java.io.*;
	import java.lang.*;
	
	public class temp
	{
		public static void main(String[] args)
		{
			InputReader in = new InputReader(System.in);
			PrintWriter pw = new PrintWriter(System.out);
			
			long n = in.nextLong();
			String s = "";
			long temp = n, sum = 0, b = 0, a = 0;
			
			while(temp>=10)
			{
				sum += 9;
				s += '9';
				temp /= 10;
			}
			
			s += temp-1;
			sum += temp - 1;
			s = StringReverse(s);
			
			a = Long.parseLong(s);
			b = n - a;
			
			while(b>0)
			{
				sum += b%10;
				b /= 10;
			}
			
			pw.print(sum);;
			
			pw.flush();
			pw.close();
		}
	
		public static String StringReverse(String s)
		{
			int l = s.length();
			String ans = "";
			
			for(int i=l-1;i>=0;i--)
			{
				ans += s.charAt(i);
			}
			
			return ans;
		}
		static class InputReader 
		{
			 
			private final InputStream stream;
			private final byte[] buf = new byte[8192];
			private int curChar, snumChars;
			private SpaceCharFilter filter;
	 
			public InputReader(InputStream stream) 
			{
				this.stream = stream;
			}
	 
			public int snext() 
			{
				if (snumChars == -1)
					throw new InputMismatchException();
				if (curChar >= snumChars) 
				{
					curChar = 0;
					try 
					{
						snumChars = stream.read(buf);
					} 
					catch (IOException e) 
					{
						throw new InputMismatchException();
					}
					if (snumChars <= 0)
						return -1;
				}
				return buf[curChar++];
			}
	 
			public int nextInt() 
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				int sgn = 1;
				if (c == '-')
			    {
					sgn = -1;
					c = snext();
				}
				int res = 0;
				do 
				{
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}
	 
			public long nextLong()
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				int sgn = 1;
				if (c == '-') 
				{
					sgn = -1;
					c = snext();
				}
				long res = 0;
				do 
				{
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = snext();
				} while (!isSpaceChar(c));
				return res * sgn;
			}
	 
			public int[] nextIntArray(int n) 
			{
				int a[] = new int[n];
				for (int i = 0; i < n; i++) 
				{
					a[i] = nextInt();
				}
				return a;
			}
	 
			public String readString()
		    {
				int c = snext();
				while (isSpaceChar(c)) 
				{
					c = snext();
				}
				StringBuilder res = new StringBuilder();
				do 
				{
					res.appendCodePoint(c);
					c = snext();
				} while (!isSpaceChar(c));
				return res.toString();
			}
	 
			public String nextLine() 
			{
				int c = snext();
				while (isSpaceChar(c))
					c = snext();
				StringBuilder res = new StringBuilder();
				do 
				{
					res.appendCodePoint(c);
					c = snext();
				} while (!isEndOfLine(c));
				return res.toString();
			}
	 
			public boolean isSpaceChar(int c) 
			{
				if (filter != null)
					return filter.isSpaceChar(c);
				return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
			}
	 
			private boolean isEndOfLine(int c) 
			{
				return c == '\n' || c == '\r' || c == -1;
			}
	 
			public interface SpaceCharFilter
		    {
				public boolean isSpaceChar(int ch);
			}
		}
		
		
		
		
		public static long mod = 1000000007;
		public static int d;
		public static int p;
		public static int q;
		
		public static  int gcd(int a, int b)
		{
		    if (a == 0)
		        return b;
		    return gcd(b%a, a);
		}
		public static int findGCD(int arr[], int n)
		{
		    int result = arr[0];
		    for (int i=1; i<n; i++)
		        result = gcd(arr[i], result);
		 
		    return result;
		}
		
	
	    public static long lcm(int[] numbers) {
	        long lcm = 1;
	        int divisor = 2;
	        while (true) {
	            int cnt = 0;
	            boolean divisible = false;
	            for (int i = 0; i < numbers.length; i++) {
	                if (numbers[i] == 0) {
	                    return 0;
	                } else if (numbers[i] < 0) {
	                    numbers[i] = numbers[i] * (-1);
	                }
	                if (numbers[i] == 1) {
	                    cnt++;
	                }
	                if (numbers[i] % divisor == 0) {
	                    divisible = true;
	                    numbers[i] = numbers[i] / divisor;
	                }
	            }
	            if (divisible) {
	                lcm = lcm * divisor;
	            } else {
	                divisor++;
	            }
	            if (cnt == numbers.length) {
	                return lcm;
	            }
	        }
	    }
		public static long fact(long n) {
			
			long factorial = 1;
			 for(int i = 1; i <= n; i++)
		        {
		            factorial *= i;
		        }
			 return factorial;
		}
		
		
		
		public static int lowerLimit(int[] a, int n) {
			int ans = 0;
			
			int ll = 0;
			int rl = a.length-1;
		//	System.out.println(a[rl]+" "+n);
			if(a[0]>n)
				return 0;
			if(a[0]==n)
				return 1;
			else if(a[rl]<=n)
				return rl+1;
		
			while(ll<=rl)
			{
				
				int mid = (ll+rl)/2;
				if(a[mid]==n)
				{
					ans = mid + 1;
					break;
				}
				
				else if(a[mid]>n)
				{
					rl = mid-1;
					
				}
				else
				{
					ans = mid+1;
					ll = mid+1;
				}
			}
			
			return ans; 
		}
		
		
		public static long choose(long total, long choose){
		    if(total < choose)
		        return 0;
		    if(choose == 0 || choose == total)
		        return 1;
		    return (choose(total-1,choose-1)+choose(total-1,choose))%mod;
		}
		
		public static int[] suffle(int[] a,Random gen)
		{
			int n = a.length;
			for(int i=0;i<n;i++)
			{
				int ind = gen.nextInt(n-i)+i;
				int temp = a[ind];
				a[ind] = a[i];
				a[i] = temp;
			}
			return a;
		}
		
		public static int floorSearch(int arr[], int low, int high, int x)
		{
		    if (low > high)
		        return -1;
		 
		    if (x > arr[high])
		        return high;
		    int mid = (low+high)/2;
		 
		 
		    if (mid > 0 && arr[mid-1] < x && x < arr[mid])
		        return mid-1;
		 
		    if (x < arr[mid])
		        return floorSearch(arr, low, mid-1, x);
		 
		    return floorSearch(arr, mid+1, high, x);
		}
		
		
		public static void swap(int a, int b){
			int temp = a;
			a = b;
			b = temp;
		}
		
		public static ArrayList<Integer> primeFactorization(int n)
		{
			ArrayList<Integer> a = new ArrayList<Integer>();
			
			for(int i=2;i*i<=n;i++)
			{
				while(n%i==0)
				{
					a.add(i);
					n/=i;
				}
			}
			if(n!=1)
				a.add(n);
			return a;
		}
		
		public static ArrayList Divisors(long n)
		{
		    ArrayList<Long> div = new ArrayList<>();
		    
		    for (int i=1; i<=Math.sqrt(n); i++)
		    {
		        if (n%i == 0)
		        {
		        	div.add((long)i);
		                
		            if(n/i != i)
		            	div.add((long)n/i);
		        }
		    }
		    return div;
		}
		
		public static void sieve(boolean[] isPrime,int n)
		{
			for(int i=1;i<n;i++)
				isPrime[i] = true;
			
			isPrime[0] = false;
			isPrime[1] = false;
			
			for(int i=2;i*i<n;i++)
			{
				if(isPrime[i] == true)
				{
					for(int j=(i*i);j<n;j+=i)
						isPrime[j] = false;
				}
			}
		}
		
		public static int GCD(int a,int b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static long GCD(long a,long b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static long LCM(long a,long b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static int LCM(int a,int b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static void extendedEuclid(int A,int B)
		{
			if(B==0)
			{
				d = A;
				p = 1 ;
				q = 0;
			}
			else
			{
				extendedEuclid(B, A%B);
				int temp = p;
				p = q;
				q = temp - (A/B)*q;
			}
		}
		
		public static int binaryExponentiation(int x,int n)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=x*x;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long binaryExponentiation(long x,long n)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=(x%mod * x%mod)%mod;
		        n=n/2;
		    }
		    return result;
		}
		
		public static int modularExponentiation(int x,int n,int M)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result * x)%M;
		        x=(x*x)%M;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long modularExponentiation(long x,long n,long M)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result * x)%M;
		        x=(x*x)%M;
		        n=n/2;
		    }
		    return result;
		}
		
		public static int modInverse(int A,int M)
		{
		    return modularExponentiation(A,M-2,M);
		}
		
		public static long modInverse(long A,long M)
		{
		    return modularExponentiation(A,M-2,M);
		}
		
		public static boolean isPrime(long n)
		{
		    
		    if (n <= 1)  return false;
		    if (n <= 3)  return true;
		    
		    if (n%2 == 0 || n%3 == 0) 
		    	return false;
		 
		    for (long i=5; i*i<=n; i=i+6)
		    {
		        if (n%i == 0 || n%(i+2) == 0)
		           return false;
		    }
		    
		    return true;
		}
		
		static class pair implements Comparable<pair>
		{
			Integer x, y;
			pair(int x,int y)
			{
				this.x=x;
				this.y=y;
			}
			
			public int compareTo(pair o) {
				int result = x.compareTo(o.x);
				if(result==0)
					result = y.compareTo(o.y);
				
				return result;
			}  
			
			public String toString()
			{
				return x+" "+y;
			}
			
			public boolean equals(Object o)
			{
				if (o instanceof pair)
			    {
					pair p = (pair)o;
					return p.x == x && p.y == y ;
				}
				return false;
			}
			
			public int hashCode()
			{
				return new Long(x).hashCode()*31 + new Long(y).hashCode();
			}
		}
		
		public static boolean palindrome(int i,int j,String s)
		{
			while(i<j)
			{
				if(s.charAt(i)==s.charAt(j))
				{
					i++;
					j--;
				}
				else
					return false;
			}
			return true;
		}
		
		static class CodeX {
	        public static void sort(int arr[]) {
	            merge_sort(arr, 0, arr.length - 1);
	        }

	        private static void merge_sort(int A[], int start, int end) {
	            if (start < end) {
	                int mid = (start + end) / 2;
	                merge_sort(A, start, mid);
	                merge_sort(A, mid + 1, end);
	                merge(A, start, mid, end);
	            }

	        }

	        private static void merge(int A[], int start,int mid, int end) {
	            int p = start, q = mid + 1;
	            int Arr[] = new int[(end - start + 1)];
	            int k = 0;

	            for (int i = start; i <= end; i++) {
	                if (p > mid)
	                    Arr[k++] = A[q++];

	                else if (q > end)
	                    Arr[k++] = A[p++];

	                else if (A[p] < A[q])
	                    Arr[k++] = A[p++];

	                else
	                    Arr[k++] = A[q++];
	            }
	            for (int i = 0; i < k; i++) {
	                A[start++] = Arr[i];
	            }

	        }

	    }
		

		
		/*static class CodeX {
	        public static void sort(long arr[]) {
	            merge_sort(arr, 0, arr.length - 1);
	        }

	        private static void merge_sort(long A[], long start, long end) {
	            if (start < end) {
	                long mid = (start + end) / 2;
	                merge_sort(A, start, mid);
	                merge_sort(A, mid + 1, end);
	                merge(A, start, mid, end);
	            }

	        }

	        private static void merge(long A[], long start,long mid, long end) {
	            long p = start, q = mid + 1;
	            long Arr[] = new long[(int)(end - start + 1)];
	            long k = 0;

	            for (int i = (int)start; i <= end; i++) {
	                if (p > mid)
	                    Arr[(int)k++] = A[(int)q++];

	                else if (q > end)
	                    Arr[(int)k++] = A[(int)p++];

	                else if (A[(int)p] < A[(int)q])
	                    Arr[(int)k++] = A[(int)p++];

	                else
	                    Arr[(int)k++] = A[(int)q++];
	            }
	            for (int i = 0; i < k; i++) {
	                A[(int)start++] = Arr[i];
	            }

	        }

	    }*/
	}