using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace AtcoderC
{
    class Program
    {
        /*static void Main(string[] args)
        {
        }*/
        //ABC132C
        //全探索法
        /*static void Main()
        {
            BigInteger N = int.Parse(Console.ReadLine());
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int min = input.Min();
            int max = input.Max();
            int countARC = 0;
            int countABC = 0;
            int Answer = 0;
            for (int i = min; i <= max; i++)
            {
                countABC = 0;
                countARC = 0;
                foreach (int n in input)
                {
                    if (n > i)
                    {
                        countARC++;
                    }
                    else
                    {
                        countABC++;
                    }
                }
                if (countABC == countARC)
                {
                    Answer++;
                }
            }
            Console.WriteLine(Answer);
        }*/
        //2回目
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Array.Sort(input);
            int min = input[(N / 2) - 1];
            int max = input[N / 2];
            Console.WriteLine(max - min);
        }*/

        //ABC131C
        //ユーグリッドの互除法の応用
        /*static void Main()
        {
            BigInteger[] input = Console.ReadLine().Split().Select(BigInteger.Parse).ToArray();
            BigInteger A = input[0];
            BigInteger B = input[1];
            BigInteger C = input[2];
            BigInteger D = input[3];
            BigInteger ans = (B / C) + (B / D);           
            //最小公倍数
            var ans2 = C * D / lcm(C, D);
            BigInteger ans3 = B / ans2;
            var BB = B - ans + ans3;
            ans = (A - 1) / C + (A - 1) / D;
            ans3 = (A - 1) / ans2;
            var AA = (A - 1) - ans + ans3;
            Console.WriteLine(BB - AA);
            
        }
        static public BigInteger lcm(BigInteger a, BigInteger b)
        {
            var r = a % b;
            while (r != 0)
            {
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }*/

        //129C
        //動的計画法
        //TLEになる時間がかかり過ぎる
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            List<int> ttt = new List<int>();
            for (int i = 0;i < M;i++)
            {
                var temp = int.Parse(Console.ReadLine());
                ttt.Add(temp);
            }
            int[] dparray = new int[N+2];
            dparray[N] = 1;
            dparray[N - 1] = 1;
            for (int i = N-1; i >= 0; i--)
            {
                if (ttt.Contains(i))
                {
                    dparray[i] = 0;
                }
                dparray[i] = (dparray[i + 1] + dparray[i + 2]) % 1000000007;
            }
            Console.WriteLine(dparray[0]);
        }*/
        //ABC128
        /*static void Main()
        {

        }*/
        //ABC134A
        /*static void Main()
        {
            int r = int.Parse(Console.ReadLine());
            var ans = 3 * r * r;
            Console.WriteLine(ans);
        }*/
        //ABC134B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int D = input[1];
            int count = 0;
            int ans = N;
            while (true)
            {
                ans = ans - (D * 2 + 1);
                count++;
                if (ans <= 0)
                {
                    break;
                }
            }
            Console.WriteLine(count);
        }*/
        //ABC134C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<int> array = new List<int>();
            for (int i =0;i<N; i++)
            {
                array.Add(int.Parse(Console.ReadLine()));
            }
            List<int> ans = new List<int>();
            int max = array.Max();
            var temp  = new List<int>();
            foreach (int n in array)
            {
                 temp.Add(n);
            }
            temp.Sort();
            temp.Reverse();
            int second = temp[1];

            foreach (int nn in array)
            {
                if (nn == max)
                {
                    Console.WriteLine(second);
                }
                else
                {
                    Console.WriteLine(max);
                }
            }
        }*/
        //134ABCD
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int count = 0;
            int ans = 0;
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i = 0;i<N;i++)
            {
                for (int j =0;j<N; j++)
                {
                    if ((j+1)%(i+1)==0)
                    {
                        count += input[j];
                    }
                }
                if (count % 2 == input[i])
                {
                    ans++;
                }
                count = 0;
            }
            if (ans != 0)
            {

            }
        }*/
        //AGC036
        /*static void Main()
        {
            long S = long.Parse(Console.ReadLine());
            long X1 = 1000000000;
            long Y1 = 0;
            /*while (true)
            {
                Y1 = S / X1 + S % X1;
            }
            Y1 = S / X1 + S % X1;
            Console.WriteLine("0 0 " + X1 + " 0 0 " + Y1); 
            /*int tempX = 0;
            List<long> ss = new List<long>();
            while (tempX < S)
            {
                var ans = S % tempX;
                if (ans == 0)
                {
                    ss.Add(ans);
                }
                tempX++;
            }
            Console.WriteLine(tempX);*/
        /*long X1 = 0;
        long Y1 = 1;
        while (true)
        {
            X1 = S % Y1;
            if (X1 <= 1000000000)
            {
                break;
            }
            Y1++;
        }
        Console.WriteLine("0 0 "+X1+" 0 0 "+Y1);
    }*/
        //ABC82A
        /*static void Main()
        {
            double[] input = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double a = input[0];
            double b = input[1];
            double sum = (a + b) / 2;
            Console.WriteLine(Math.Ceiling(sum));

        }*/
        //ABC128C
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int ans = 0;
            List<int[]> K = new List<int[]>();
            for (int i = 0;i<M;i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                K.Add(temp);
            }
            int[] P = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] light = new int[M];
            for (int i = 0;i < Math.Pow(2,N);i++)
            {
                var isrow = 0;
                var temp = int.Parse(Convert.ToString(i, 2)).ToString("0000000000");
                for (int j  =0;j < M;j++)
                {
                    var ison = 0;
                    for (int k = 0; k < K[j][0];k++)
                    {
                        var index = K[j][k] - 1;
                        if (temp[9-index] == '1')
                        {
                            ison++;
                        }
                    }
                    if (ison % 2 == P[j])
                    {
                        isrow++;
                    }
                    else
                    {
                        break;
                    }
                }
                if (isrow == M)
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);*/
        /*nt[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int a = input[0];
        int b = input[1];
        var temp = a * b % 2;
        if (temp == 0)
        {
            Console.WriteLine("even");
        }
        else
        {
            Console.WriteLine("odd");
        }
    }*/
        //ABC127C 
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            List<int[]> gate = new List<int[]>();
            for (int i = 0; i < M; i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                gate.Add(temp);
            }
            if (M == 1)
            {
                Console.WriteLine(N);

            }
            else
            {
                List<int> card = new List<int>();
                for (int i = gate[0][0]; i <= gate[0][1]; i++)
                {
                    card.Add(i);
                }

                for (int j = 1; j < gate.Count; j++)
                {
                    List<int> ans = new List<int>();
                    var count = 0;
                    for (int i = gate[j][0]; i <= gate[j][1]; i++)
                    {
                        if (card.Contains(i))
                        {
                            count++;
                            ans.Add(i);
                        }
                    }
                    if (count == 0)
                    {
                        break;
                    }
                    card = new List<int>(ans);
                }
                Console.WriteLine(card.Count());
            }
        }*/
        //127C Revenge TLE
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            List<int[]> gate = new List<int[]>();
            for (int i = 0; i < M; i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                gate.Add(temp);
            }
            int Ans = 0;
            for (int i =1;i<=N;i++)
            {
                var count = 0;
                for (int j = 0;j < gate.Count;j++)
                {
                    if (gate[j][0] <= i && i <= gate[j][1])
                    {
                        count++;
                    }  
                }
                if (count == gate.Count)
                {
                    Ans++;
                }
            }
            Console.WriteLine(Ans);
        }*/
        //127C RevengeVer2
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            List<int[]> gate = new List<int[]>();
            for (int i = 0; i < M; i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                gate.Add(temp);
            }
            List<int> Max = new List<int>();
            List<int> Min = new List<int>();
            for (int i =0;i< M;i++)
            {
                Max.Add(gate[i][1]);
                Min.Add(gate[i][0]);
            }
            int max = Max.Min();
            int min  = Min.Max();
            if (min <= max)
            {
                Console.WriteLine(max - min + 1);
            }
            else
            {
                Console.WriteLine("0");
            }
        }*/
        //ABC126C
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            double ans = 0.0;
            for (int i = 1; i<= N;i++)
            {
                double tempP = (double)1 / N;
                int point = i;
                while (point<M)
                {
                    tempP = tempP * 1 / 2;
                    point *= 2;
                }
                ans += tempP;
            }
            Console.WriteLine(ans);
        }*/
        //ABC125C ユーグリッド互除法
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Array.Sort(A);
            int lcmr, lcml = 0;
            List<int> answer = new List<int>();
            for (int i =0;i<A.Length;i++)
            {
                lcmr = 0;
                for (int x = 0;x < i;x++)
                {
                    if (lcmr - A[x] >= 0)
                    {
                        lcmr = lcm(lcmr, A[x]);
                    }
                    else
                    {
                        lcmr = lcm(A[x], lcmr);
                    }
                }
                lcml = 0;
                for (int y = i+1; y < A.Length; y++)
                {
                    if (lcml - A[y] >= 0)
                    {
                        lcml = lcm(lcml, A[y]);
                    }
                    else
                    {
                        lcml = lcm(A[y],lcml);
                    }
                }
                var tempans = 0;
                if (lcmr > lcml)
                {
                   tempans = lcm(lcmr, lcml);
                }
                else
                {
                   tempans = lcm(lcml, lcmr);
                }
                answer.Add(tempans);
            }
            Console.WriteLine(answer.Max());
        }
        static public int lcm(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            var r = a % b;
            while (r != 0)
            {
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }*/

        //124C
        /*static void Main()
        {
            string inputstr = Console.ReadLine();
            int count = 0;
            if (inputstr[0] == '0')
            {
                for (int i = 0; i < inputstr.Length; i++)
                {
                    if (i % 2 == 0)
                    {
                        if (inputstr[i] == '1')
                        {
                            count++;
                        }
                    }
                    else
                    {
                        if (inputstr[i] == '0')
                        {
                            count++;
                        }
                    }
                }
            }
            else
            {
                for (int i = 0; i < inputstr.Length; i++)
                {
                    if (i % 2 == 1)
                    {
                        if (inputstr[i] == '1')
                        {
                            count++;
                        }
                    }
                    else
                    {
                        if (inputstr[i] == '0')
                        {
                            count++;
                        }
                    }
                }
            }
            Console.WriteLine(count);
        }*/
        //123C 
        /*static void Main()
        {
            double N = double.Parse(Console.ReadLine());
            List<double> city = new List<double>();
            for (int i = 0; i < 5; i++)
            {
                city.Add(double.Parse(Console.ReadLine()));
            }
            var ans = Math.Ceiling(N / city.Min()) + 4;
            Console.WriteLine(ans);
        }*/
        //82C
        /*static void Main()
        {
            double[] input = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double a = input[0];
            double b = input[1];
            double answer = (a + b) / 2;
            Console.WriteLine(Math.Ceiling(answer));
        }*/
        //128B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int P = input[1];
            var ans = (P + A * 3) / 2;
            Console.WriteLine(ans);
            int a,b
            cin << a << b;
            cout >> (P + A * 3) / 2 >> endl;
        }*/
        //119A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            if (B % A == 0)
            {
                Console.WriteLine(A + B);
            }
            else
            {
                Console.WriteLine(B-A);
            }
        }*/
        //116A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            int C = input[2];
            Console.WriteLine((A*B)/2);
        }*/
        //ABC31B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = int.Parse(Console.ReadLine());
            List<int> array = new List<int>();
            for (int i =0;i<N;i++)
            {
                array.Add(int.Parse(Console.ReadLine()));
            }
            foreach (int a in array)
            {
                if (a < input[0])
                {
                    Console.WriteLine(input[0] - a);
                }
                else if (input[1] < a)
                {
                    Console.WriteLine("-1");
                }
                else
                {
                    Console.WriteLine("0");
                }
            }
        }*/
        //ABC36B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<string> map = new List<string>();
            for (int i =0;i< N;i++)
            {
                map.Add(Console.ReadLine());
            }
            List<string> ans = new List<string>();
            for(int j = 0; j  < N;j++)
            {
                var temp = "";
                for (int i = N-1; i >= 0; i--)
                {
                    temp += map[i][j];
                }
                ans.Add(temp);
            }
            foreach (string a in ans)
            {
                Console.WriteLine(a);
            }
        }*/
        //ABC40B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int A = 0;
            int temp = N;
            if (N == 1)
            {
                Console.WriteLine("0");
            }
            else
            {
                while (true)
                {
                    double root = Math.Sqrt(N);
                    if (root != (int)root)
                    {
                        N--;
                    }
                    else
                    {
                        A = (int)root;
                        break;
                    }
                }
                List<int> answer = new List<int>();
                bool flag = false;
                while (A > 0)
                {
                    var a = A;
                    while (A * a <= temp)
                    {
                        var ans = temp - (A * a) + Math.Abs(A - a);
                        if (ans == 0)
                        {
                            flag = true;
                            break;
                        }
                        a++;
                        answer.Add(ans);
                    }
                    if (flag == true)
                    {
                        break;
                    }
                    A--;
                }
                if (flag)
                {
                    Console.WriteLine("0");
                }
                else
                {
                    Console.WriteLine(answer.Min());
                }
            }
        }*/
        //ABC122C
        //TLE
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            string S = Console.ReadLine();
            List<int[]> array = new List<int[]>();
            for (int i = 0; i < input[1]; i++)
            {
                array.Add(Console.ReadLine().Split().Select(int.Parse).ToArray());
            }
            List<int> answer = new List<int>();
            foreach (int[] n in array)
            {
                var tempstr = S.Substring(n[0]-1,n[1]-n[0]+1);
                var count = tempstr.Length - tempstr.Replace("AC","").Length;
                var ans = count / 2;
                answer.Add(ans);
            }
            foreach (int a in answer)
            {
                Console.WriteLine(a);
            }
        }*/
        /*static void Main()
        { 
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            string S = Console.ReadLine();
            List<int[]> array = new List<int[]>();
            for (int i = 0; i < input[1]; i++)
            {
                array.Add(Console.ReadLine().Split().Select(int.Parse).ToArray());
            }
            for (int i = 0;i < S.Length-1;i++)
            {
                if (S[i] == 'A')
                {
                    if (S[i + 1] == 'C')
                    {
                        S = S.Replace(S[i],'a');
                    }
                }
            }
            int count = 0;
            List<int> ansstr = new List<int>();
            for (int i = 0; i < S.Length;i++)
            {
                count = 0;
                for (int j = 0;j <= i;j++)
                {
                    if (S[j] == 'a')
                    {
                        count++;
                    }
                }
                ansstr.Add(count);
            }
            List<int> anss = new List<int>();
            for (int i = 0; i < input[1];i++)
            {
                anss.Add(ansstr[array[i][1]-2] - ansstr[array[i][0]-1]);
            }
            foreach (int a in anss)
            {
                Console.WriteLine(a);
            }
        }*/
        //ABC39B
        /*static void Main()
        {
            int X = int.Parse(Console.ReadLine());
            var ans = Math.Sqrt(X);
            var ans2 = Math.Sqrt(ans);
            Console.WriteLine(ans2);
        }*/
        //ABC38B
        /*static void Main()
        {
            int[] input1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] input2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            bool flag1 = false;
            foreach (int a in input1)
            {
                foreach (int b in input2)
                {
                    if (a == b)
                    {
                        flag1 = true;
                    }
                }
            }
            if (flag1 == true)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }*/
        //ABC35B
        /*static void Main()
        {
            string S = Console.ReadLine();
            int T = int.Parse(Console.ReadLine());
            int[] pos = { 0, 0 };
            foreach (char a in S)
            {

            }
        }*/
        //ABC34B
        /*static void Main()
        {

        }*/
        //技術ProgramContest4Day1
        //A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();

        }*/
        //ABC135A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            var temp = B - A;
            if (temp % 2 == 0)
            {
                Console.WriteLine(A + (temp/2));
            }
            else
            {
                Console.WriteLine("IMPOSSIBLE");
            }
        }*/
        //ABC135B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] P = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] AnsN = new int[N];
            for (int i = 0;i <N;i++)
            {
                AnsN[i] = i + 1; 
            }
            int count = 0;
            for(int i = 0;i < N;i++)
            {
                if (P[i] != AnsN[i])
                {
                    count++;
                }
            }
            if (count <= 2)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }*/
        //ABC135C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] B = Console.ReadLine().Split().Select(int.Parse).ToArray();
            /*int count = 0;
            for (int i = N;i>0;i--)
            {
                var tempA = A[i] + A[i - 1];
                if (tempA <= B[i - 1])
                {
                    A[i - 1] = 0;
                    count += tempA;
                }
                else
                {
                    if (A[i] <= B[i - 1])
                    {
                        A[i - 1] = tempA - B[i - 1];
                        count += B[i - 1];
                    }
                    else
                    {
                        count += B[i - 1]; 
                    }
                }
            }*/
        /*int count = 0;
        for (int i = 0;i < N;i++)
        {
            var tempA = A[i] + A[i + 1];
            if (tempA <= B[i])
            {
                A[i + 1] = 0;
                count += tempA;
            }
            else
            {
                if (B[i] >= A[i])
                {
                    A[i + 1] = A[i + 1] - (B[i] - A[i]);
                    count += B[i];
                }
                else
                {
                    count += B[i]; 
                }
            }
        }
        //このやり方
        int count = 0;
        for (int i = 0; i < N;i++)
        {
            List<int> temp = new List<int>();
            temp.Add(A[i]);
            temp.Add(B[i]);
            count += temp.Min();

        }
        Console.WriteLine(count);
    }*/
        //ABC135D

        //ABC127A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            string inputstr = Console.ReadLine();
            char[] temp = inputstr.ToCharArray();
            temp[input[1]-1] =  Char.ToLower(temp[input[1] -1]);
            inputstr = new string(temp);
            Console.WriteLine(inputstr);
        }*/
        //ABC35
        /*static void Main()
        {
            string S = Console.ReadLine();
            int T = int.Parse(Console.ReadLine());
            int[] ans = { 0, 0 };
            int count = 0;
            for (int i = 0; i < S.Length;i++)
            {
                if (S[i] == 'U')
                {
                    ans[1]++;
                }
                else if (S[i] == 'D')
                {
                    ans[1]--;
                }
                else if (S[i] == 'R')
                {
                    ans[0]++;
                }
                else if (S[i] == 'L')
                {
                    ans[0]--;
                }
                else
                {
                    count++;
                }
            }
            List<int[]> answer = new List<int[]>();
            answer.Add(ans);
            answer.Add(ans);
            answer.Add(ans);
            answer.Add(ans);
            foreach (int[] n in answer)
            {
                
            }
      
        }*/
        //ABC114A
        /*static void Main()
        {
            int x = int.Parse(Console.ReadLine());
            if (x == 7 || x == 5 || x == 3)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }*/
        //ABC121C
        //TLE
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long n = input[0];
            long M = input[1];
            List<long[]> shop = new List<long[]>();
            for (int i = 0;i < n;i++)
            {
                shop.Add(Console.ReadLine().Split().Select(long.Parse) .ToArray());
            }
            List<long[]> answer = new List<long[]>(Sort(shop));
            long price = 0;
            long count = 0;
            foreach (long[] temp in answer)
            {
                var tempcount = count;
                if (count + temp[1] <= M)
                {
                    count += temp[1];
                }
                else
                {
                    count = M;
                }
                price += (count-tempcount) * temp[0];
                if (M<=count)
                {
                    break;
                }
            }
            Console.WriteLine(price);
        }
        static List<long[]> Sort(List<long[]> A)
        {
            for (int i = 0;i < A.Count;i++)
            {
                for (int j = A.Count-1;j >i;j-- )
                {
                    if (A[j][0] < A[j-1][0])
                    {
                        var temp = A[j];
                        A[j] = A[j - 1];
                        A[j - 1] = temp;
                    }
                }
            }
            return A;
        }*/
        //Sortはライブラリを使った方が早い
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long n = input[0];
            long M = input[1];
            List<long[]> shops = new List<long[]>();
            for (int i = 0; i < n; i++)
            {
                shops.Add(Console.ReadLine().Split().Select(long.Parse).ToArray());
            }
            long count = 0;
            long ans = 0;
            foreach (long[] shop in shops.OrderBy(a => a[0]))
            {
                var i = Math.Min(M - count, shop[1]);
                ans += shop[0] * i;
                count += i;
                if (count >= M)
                {
                    break;
                }
            }
            Console.WriteLine(ans);
        }*/
        //120C
        //TLE
        /*static void Main()
        {
            /*string input = Console.ReadLine();
            int len = input.Length;
            int count = 0;
            while (input.Contains("01") || input.Contains("10"))
            {
                input = input.Replace("01", "").Replace("10", "");
                count += len - input.Length;
                len = input.Length;
            }
            Console.WriteLine(count);


            string s = Console.ReadLine();
            int zero = s.Replace("1", "").Length;
            int one = s.Replace("0", "").Length;
            Console.WriteLine((zero < one ? zero : one) * 2);
        }*/
        //119
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            List<int> goal = new List<int>();
            List<int> list = new List<int>();
            for (int i =1;i<=N-1;i++)
            {
                goal.Add(input[i]);
            }
            for (int i = 0;i<N;i++)
            {
                list.Add(int.Parse(Console.ReadLine()));
            }

        }*/
        //118C
        //37B
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long n = input[0];
            long k = input[1];
            List<long[]> list = new List<long[]>();
            for (int i = 0;i < k;i++)
            {
                long[] temp = Console.ReadLine().Split().Select(long.Parse).ToArray();
                list.Add(temp);
            }
            long[] Ans = new long[n];
            foreach (long[] m in list)
            {
                for (int i =0;i < Ans.Length;i++)
                {
                    if (m[0]-1 <= i && i <= m[1]-1)
                    {
                        Ans[i] = m[2];
                    }
                }
            }
            foreach (int a in Ans)
            {
                Console.WriteLine(a);
            }
        }*/
        //大手前プロコン2019
        //A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            if (A + 0.5f >= B)
            {
                Console.WriteLine("1");
            }
            else
            {
                Console.WriteLine("0");
            }
        }*/
        //E
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long N = input[0];
            long Q = input[1];
            List<long> D = new List<long>();
            for (long i = 0;i < N;i++)
            {
                D.Add(long.Parse(Console.ReadLine()));
            }
            List<long[]> TLR = new List<long[]>();
            for (long i = 0;i < Q;i++)
            {
                TLR.Add(Console.ReadLine().Split().Select(long.Parse).ToArray());
            }
       
            foreach (long[] tlr in TLR)
            {
                var count = 0;
                var tempara = new List<long>();
                var a = tlr[0];
                tempara.Add(a);
                for (long i = 1;i <= N;i++)
                {
                    if (Math.Abs(a - (-1 * i)) > D[(int)i - 1])
                    {
                        a = a - D[(int)i - 1];
                    }
                    else
                    {
                        a = -1*i;
                    }
                    tempara.Add(a);
                }
                foreach (long n in tempara) 
                {
                    if ( tlr[1]<= n && tlr[2] >= n)
                    {
                        count++;
                    }
                }
                Console.WriteLine(count);
            }

        }*/
        //AtCoderBeginnerContest136
        //136A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            int C = input[2];
            var a = A - B;
            var ans = C - a;
            if (ans >= 0)
            {
                Console.WriteLine(ans);
            }
            else
            {
                Console.WriteLine("0");
            }
        }*/
        //136B
        /*static void Main()
        {
            string N = Console.ReadLine();
            int n = int.Parse(N);
            int ocun = 0;
            for (int i = 1; i<=n;i++)
            {
                if (i.ToString().Length % 2 == 1)
                {
                    ocun++;
                }
            }
            Console.WriteLine(ocun);
        }*/
        //136C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] list = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int count = 0;
            int max = 0;
            bool flag = false;
            foreach (int a in list)
            {
                if (a >= max)
                {
                    max = a;
                }
                else if (max - a >= 2)
                {
                    flag = true;
                    break;
                }
                else { }
            }
            if (flag)
            {
                Console.WriteLine("No");
            }
            else
            {
                Console.WriteLine("Yes");
            }
        }*/
        //113C-ID
        /*static void Main()
        {
            string S = Console.ReadLine();
            Console.WriteLine(S.Length);
        }*/
        //113A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            Console.WriteLine(A + (B/2));
        }*/
        //112A 
        /*static void Main()
        {

        }*/
        //137A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            List<int> answer = new List<int>();
            var ans1 = A + B;
            answer.Add(ans1);
            var ans2 = A - B;
            answer.Add(ans2);
            var ans3 = A * B;
            answer.Add(ans3);
            Console.WriteLine(answer.Max());
        }*/
        //137B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int K = input[0];
            int X = input[1];
            for (int i = X - (K-1);i<= X + (K-1);i++)
            {int 
                if (i >= -1000000 && i <= 1000000)
                {
                    Console.Write(i+" ");
                }

            }
            Console.WriteLine();
        }*/
        //137C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<string[]> list = new List<string[]>();
            for (int i = 0; i < N;i++)
            {
                list.Add(Console.ReadLine().Split());
            }
            foreach (string[] n in list)
            {
                Array.Sort(n);
            }
            long ans = 0;
            for (int i  = 0; i< list.Count;i++)
            {
                for (int j = i+1;j < list.Count;j++)
                {
                    if (list[i].Equals(list[j]))
                    {
                        ans++;
                    }
                }
            }
            Console.WriteLine(ans);
        }*/
        /*static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            string[] S = new string[N];
            for (var i = 0; i < N; i++)
            {
                char[] c = Console.ReadLine().ToCharArray();
                Array.Sort(c);
                S[i] = new string(c);
            }

            Dictionary<string, long> dict = new Dictionary<string, long>();
            for (var i = 0; i < N; i++)
            {
                if (dict.ContainsKey(S[i]))
                {
                    dict[S[i]]++;
                }
                else
                {
                    dict[S[i]] = 1L;
                }
            }
            long res = 0L;
            foreach (var i in dict)
            {
                if (i.Value > 1)
                {
                    res += i.Value * (i.Value - 1) / 2;
                }
            }
            Console.WriteLine(res);
        }*/
        //138A
        /*static void Main()
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            if (a < 3200)
            {
                Console.WriteLine("red");
            }
            else
            {
                Console.WriteLine(s);
            }
        }*/
        //138B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            double[] A = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double ans = 0;
            for (int i = 0;i<A.Length;i++)
            {
                ans += 1 / A[i];
            }
            Console.WriteLine(1/ans);
        }*/
        //138C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            double[] v = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double ans = 0;
            Array.Sort(v);
            ans = (v[0] + v[1]) / 2;
            for (int i = 2; i < N;i++)
            {
                ans = (ans + v[i]) / 2;
            }
            Console.WriteLine(ans);
        }*/
        //138D
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int Q = input[1];
            List<Data> datalist = new List<Data>();
            List<int[]> listQ = new List<int[]>();
            for (int i = 0; i < N-1;i++)
            {
                Data data = new Data();
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                data.a = temp[0];
                data.b = temp[1];
                datalist.Add(data);
            }
            datalist = datalist.OrderBy(n => n.a).OrderBy(m => m.b).ToList();
            for (int i = 0;i < Q;i++)
            {
                listQ.Add(Console.ReadLine().Split().Select(int.Parse).ToArray());
            }
            
            int[] Answer = new int[datalist[datalist.Count()].b];
            var tempA = 0;
            foreach (Data aa in datalist)
            {
                if (aa.a > tempA)
                {
                    tempA = aa.a;
                }
            }
            foreach (int[] temp in listQ)
            {
                if (temp[0] < tempA)
                {
                    for (int i = temp[0]; i < Answer.Length; i++)
                    {
                        Answer[i] += temp[1];
                    }
                }
                else
                {
                    Answer[temp[0]] += Answer[1];
                }
            }
            foreach (int a in Answer)
            {
                Console.Write(a);
            }
            Console.WriteLine();
        }*/
        //最強プログラマ―選手権
        //A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int M = input[0];
            int D = input[1];
            int ans = 0;
            for (int i = 1;i <= M;i++)
            {
                for (int j = 1; j <= D; j++)
                {
                    int d1 = j / 10;
                    int d2 = j % 10;
                    if (d1 >= 2 && d2 >= 2)
                    {
                        var temp = d1 * d2;
                        if (temp == i)
                        {
                            ans++;
                        }
                    }
                }
            }
            Console.WriteLine(ans);
        }*/
        //B
        /*static void Main()
        {
            var tem = 1000000007;
            var input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = input[0];
            var K = input[1];
            var array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var invert = new long[N];
            for (int i =0;i<N;i++)
            {

                for (int j = i+1;j < N;j++)
                {
                    if (array[i] > array[j])
                    {
                        invert[i]++;
                    }
                }
            }
            var less = new long[N];
            for (int i = 0; i < N; i++)
            {

                for (int j = 0; j < N; j++)
                {
                    if (array[i] > array[j])
                    {
                        less[i]++;
                    }
                }
            }
            long ans = 0;
            for (int i = 0;i < N;i++)
            {
                ans = (ans + (invert[i] * K) % tem) % tem;
                ans = (ans + (less[i] * ((K * (K-1))/ 2 % tem)) % tem) % tem;
                //K*(K-1)/2
            }
            Console.WriteLine(ans %tem);
        }*/
        //139A
        /*static void Main()
        {
            string input = Console.ReadLine();
            string input2 = Console.ReadLine();
            int ans = 0;
            for (int i = 0;i < input.Length;i++)
            {
                if (input[i] == input2[i])
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);
        }*/
        //139B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            var ans = 0;
            var temp = 1;
            while (temp < B)
            {
                --temp;
                temp+= A;
                ++ans;
            }
            Console.WriteLine(ans);
        }*/
        //139C
        /*static void Main()
        {
            int N =int.Parse(Console.ReadLine());
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            List<long> sa = new List<long>();
            for (long i = 0;i < input.Length - 1;i++)
            {
                if (input[i] >= input[i + 1])
                {
                    sa.Add(1);
                }
                else
                {
                    sa.Add(0);
                }
            }
            var count = 0;
            List<long> Answer = new List<long>();
            for(int i = 0; i < sa.Count;i++)
            {
                if (sa[i] == 1)
                {
                    count++;
                }
                else {
                    count = 0;
                }
                Answer.Add(count);
            }
            Console.WriteLine(Answer.Max());
        }*/
        //140A
        /*static void Main()
        {
            double input = double.Parse(Console.ReadLine());
            var ans = Math.Pow(input, 3);
            Console.WriteLine(ans);                    
        }*/
        //140B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] B = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] C = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int Ans = 0;
            for (int i = 0;i < B.Length;i++)
            {
                Ans += B[i];
            }
            for (int i = 0;i <= A.Length -2;i++ )
            {
                if (A[i + 1] - A[i] == 1)
                {
                    Ans += C[A[i] - 1];
                }
            }
            Console.WriteLine(Ans);
        }*/
        //140C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] B = Console.ReadLine().Split().Select(int.Parse).ToArray();
            long Ans = 0;
            Ans += B[0];
            Ans += B[B.Length-1];
            for (int i = 0; i<B.Length-1;i++)
            {
                List<int> temp = new List<int>();
                temp.Add(B[i]);
                temp.Add(B[i + 1]);
                Ans += temp.Min();
            }
            Console.WriteLine(Ans);
        }*/
        //141A
        /*static void Main()
        {
            string temp = Console.ReadLine();
            switch (temp)
            {
                case "Sunny":
                    Console.WriteLine("Cloudy");
                    break;
                case "Cloudy":
                    Console.WriteLine("Rainy");
                    break;
                case "Rainy":
                    Console.WriteLine("Sunny");
                    break;

            }
        }*/
        //141B
        /*static void Main()
        {
            string S = Console.ReadLine();
            bool flag = false;
            for (int i = 0; i < S.Length; i++)
            {
                if (i % 2 == 0)
                {
                    if (S[i] == 'L' || S[i] == 'U' || S[i] == 'D')
                    {

                    }
                    else
                    {
                        flag = true;
                    }
                }
                else
                {
                    if (S[i] == 'R' || S[i] == 'U' || S[i] == 'D')
                    {

                    }
                    else
                    {
                        flag = true;
                    }
                }
            }
            if (flag == false)
            {
                Console.WriteLine("No");
            }
            else
            {
                Console.WriteLine("Yes");
            }
        }*/
        //142A
        /*static void Main()
        {
            double N = double.Parse(Console.ReadLine());
            double count = 0;
            for (int i = 1;i <= N;i++)
            {
                if (i % 2 == 1)
                {
                    count++;
                }
            }
            double Ans = count / N;
            Console.WriteLine(Ans);
        }*/
        //142B
        /*tatic void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int K = input[1];
            int count = 0;
            int[] h = Console.ReadLine().Split().Select(int.Parse).ToArray();
            foreach (int temp in h)
            {
                if (temp >= K)
                {
                    count++;
                }
            }
            Console.WriteLine(count);
        }*/
        //142C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] temp1 = new int[temp.Length];
            for (int i = 1;i <= temp.Length;i++)
            {
                temp1[i-1] = i;
            }
            List<int[]> ans = new List<int[]>();
            for (int i = 0; i < temp.Length;i++)
            {
                int[] aa = new int[2];
                aa[0] = temp[i];
                aa[1] = temp1[i];
                ans.Add(aa);
            }
            int[] Ans = new int[N];
            for(int i = 0;i < N;i++){
                Ans[i] = 0;
            }
            for (int i = 0; i < ans.Count; i++)
            {
                Ans[ans[i][0] - 1] = ans[i][1];
            }
            for (int i = 0;i < Ans.Length;i++) {
                Console.Write(Ans[i] + " ");
            }
            Console.WriteLine();
        }*/
        //142D
        /*static void Main()
        {
            int[] N = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = N[0];
            int B = N[1];
            List<int> temp = new List<int>();
            for (int i = 1; i <= A; i++)
            {
                if (B % i == 0)
                {
                    temp.Add(i);
                }
            }
            for (int i = 0; i < temp.Count; i++)
            {
                for (int j = i; j < temp.Count; j++)
                {

                }
            }
        }*/
        //141C
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int K = input[1];
            int Q = input[2];
            List<int> A = new List<int>();
            for (int i = 0;i < Q;i++)
            {
                A.Add(int.Parse(Console.ReadLine()));
            }
            int[] ans = new int[N];
            for (int i = 0;i < N; i++)
            {
                ans[i] = K;
            }
            int[] point = new int[N];
            for (int i = 0;i < N;i++)
            {
                point[i] = 0;
            }
            foreach (int a in A)
            {
                point[a - 1] += 1;
            }
            for(int i = 0; i < N;i++ )
            {
                point[i] = Q - point[i];
            }
            List<int> Answer = new List<int>();
            for (int j = 0; j < N;j++)
            {
                var temp  = ans[j] - point[j];
                Answer.Add(temp);
            }
            foreach (int temp in Answer)
            {
                if (temp > 0) { Console.WriteLine("Yes"); }
                else { Console.WriteLine("No"); }
            }
        }*/
        //139D
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            long Ans = 0;
            for (int i = 1;i <= N-1;i++)
            {
                Ans += i;
            }
            Console.WriteLine(Ans);
        }*/
        //133C
        /*static void Main()
        {
            int[] M = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int r = M[0];
            int l = M[1];
            var Ans = m(r, l);
            Console.WriteLine(Ans);

        }
        static long m(int r, int l)
        {
            var ans = long.MaxValue;
            for (int i = r; i < l; i++)
            {
                for (int j = i + 1; j <= l; j++)
                {
                    ans = Math.Min(ans, (i * j) % 2019);
                    if (ans == 0) { return ans; }
                }
            }
            return ans;
        }*/
        /*static void Main(string[] args)
        {
            var lr = Console.ReadLine().Split();
            var l = int.Parse(lr[0]);
            var r = int.Parse(lr[1]);

            var ans = m1(l, r);
            Console.WriteLine(ans);
        }

        static long m1(int l, int r)
        {
            var ans = long.MaxValue;

            for (long i = l; i < r; i++)
            {
                for (long j = i + 1; j <= r; j++)
                {
                    ans = Math.Min(ans, i * j % 2019);
                    if (ans == 0) return ans;
                }
            }

            return ans;
        }*/
        //学生コンテスト
        //A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] B = Console.ReadLine().Split().Select(int.Parse).ToArray();
            bool flag = false;
            List<int[]> ans1 = new List<int[]>();
            for (int i = 0; i < N;i++)
            {
                int[] tarray = new int[M];
                for (int j = 0;j < M;j++)
                {
                    var temp1 = A[i] + B[j];
                    tarray[j] = temp1;
                }
                ans1.Add(tarray);
            }
            List<int> ans = new List<int>();
            for (int i = 0; i < N;i ++ )
            {
                for (int j = 0; j < M;j++)
                {
                    ans.Add(A[i] + B[j]);
                }
            }
            var tempans = 0;
            //var aaa = ans.GroupBy(n => n).Where(n => n.Count() > 1).Select(group => group.Key).ToArray();
            ans.Sort();
            for (int i = 0;i < ans.Count -1;i++)
            {
                if (ans[i] == ans[i+1]) {
                    tempans = ans[i];
                    flag = true;
                    break;
                 }
            }
            int a1 = 0;
            int a2 = 0;
            int b1 = 0;
            int b2 = 0;
            int count = 0;
            bool temp = false;
            if (flag == true)
            {
                for (int i = 0; i < N; i++)
                {
                    if (ans1[i].Contains(tempans))
                    {
                        for (int j = 0; j < M; j++)
                        {
                            if (tempans == ans1[i][j] && count == 0)
                            {
                                a1 = i;
                                a2 = j;
                                count++;
                                break;
                            }
                            if (tempans == ans1[i][j] && count == 1)
                            {
                                b1 = i;
                                b2 = j;
                                temp = true;
                                break;
                            }
                            if (temp == true) { break; }
                        }
                    }
                }
            }
            else
            {
                Console.WriteLine("-1");
            }
            if(temp == true)
            {
                Console.WriteLine(a1 + " " + a2 + " " + b1 + " " + b2);
            }
           
        }*/
        //108C
        //全ての都市に対してMath.Abs(X-x[i])の最大公約数をもとめるプログラムになる．
        //SCIE,SCIの研究ジャーナルは信用の大会論文である．
        //じぁーなるのお話
        //参考の論文を簡単にまとめるプログラム(Mendelay)
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int X = input[1];
            long[] XList = Console.ReadLine().Split().Select(long.Parse).ToArray();
            List<long> ans = new List<long>();
            for (int i = 0;i < N;i++)
            {
                var temp = Math.Abs(XList[i]-X);
                ans.Add(temp);
            }
            for (int i = 0;i < N;i++)
            {

            }

            Console.WriteLine(ans.Min());
        }*/
        //128D
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int[] sw = Console.ReadLine().Split().Select(int.Parse).ToArray();
            List<int[]> sw2 = new List<int[]>();
            for (int i = 0;i < M;i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                sw2.Add(temp);
            }
            int[] sw3 = Console.ReadLine().Split().Select(int.Parse).ToArray();

           

        }*/
        //143A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            var ans = A - (2 * B);
            if (ans > 0)
            {
                Console.WriteLine(ans);
            }
            else
            {
                Console.WriteLine("0");
            }
        }*/
        //143B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int Answer = 0;
            for (int i = 0;i < N-1;i++)
            {
                for (int j = i+1; j < N;j++)
                {
                    var temp = input[i] * input[j];
                    Answer += temp;
                }
            }
            Console.WriteLine(Answer);
        }*/
        //143C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            var temp = S[0];
            List<string> Ans = new List<string>();
            for (int i = 1; i < N;i++)
            {
                if (temp == S[i])
                {

                    temp = S[i];
                }
                else
                {
                    Ans.Add(temp.ToString());
                    temp = S[i];
                }
            }
            Console.WriteLine(Ans.Count() + 1);
        }*/
        //143D
        /*static void Main()
        {

        }*/
        //144A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            if (A > 9 || B > 9)
            {
                Console.WriteLine("-1");
            }
            else
            {
                Console.WriteLine(A * B);
            }
        }*/
        //144B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<int> map = new List<int>();
            for (int i = 1;i < 10;i++)
            {
                for (int j = 1;j < 10;j++)
                {
                    var temp = i * j;
                    map.Add(temp);
                }
            }
            if (map.Contains(N))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }*/
        //DISCO2019A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int X = input[0];
            int Y = input[1];
            long moneyX = 0;
            long moneyY = 0;
            int count = 0;
            if (X < 4)
            {
                switch (X)
                {
                    case 1:
                        moneyX += 300000;
                        count++;
                        break;
                    case 2:
                        moneyX += 200000;
                        break;
                    case 3:
                        moneyX += 100000;
                        break;
                }
            }
            if (Y < 4)
            {
                switch (Y)
                {
                    case 1:
                        moneyY += 300000;
                        count++;
                        break;
                    case 2:
                        moneyY += 200000;
                        break;
                    case 3:
                        moneyY += 100000;
                        break;
                }
            }
            if (count == 2)
            {
                moneyX += 400000;
            }
            Console.WriteLine(moneyX + moneyY);
        }*/
        //DISCO2019B
        /*static void Main()
        {
            long N = long.Parse(Console.ReadLine());
            long[] A = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long left = 0;
            long right = 0;
            long sum = 0;
            foreach (long a in A)
            {
                sum += a;
            }
            List<long> sa = new List<long>();
            for (long i = 0;i < N;i++)
            {
                left += A[i];
                right = sum - left;
                sa.Add(Math.Abs(left - right));
            }
            sa.Sort();

            Console.WriteLine(sa[0]);
        }*/
        //DISCO2019C
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            List<string> array = new List<string>();
            for (int i = 0;i<input[1];i++)
            {
                var temp = Console.ReadLine();
                array.Add(temp);
            }
            int[,] mapp = new int[input[0], input[1]];
            int count = 1;
            for (int i = 0;i < input[0];i++)
            {
                for (int j = 0;j < input[1];j++)
                {
                    if (array[i][j] == '#')
                    {
                        mapp[i,j] += count;
                        count++;
                    }
                }
            }
            for (int i = 0; i < input[0]; i++)
            {
                for (int j = 0; j < input[1]; j++)
                {
                    if (mapp[i,j] == 0)
                    {
                        if (j == 0)
                        {
                            for (int k =0;k < input[1];k++)
                            {
                                if (mapp[i, k] != 0)
                                {
                                    mapp[i, j] = mapp[i, k];
                                    break;
                                }
                            }
                        }
                        else
                        {
                            mapp[i,j] = mapp[i, j - 1];
                        }
                    }
                }
            }
            for (int i = 0;i < input[0];i++)
            {
                for (int j = 0;j < input[1];j++)
                {
                    if (mapp[i,j] == 0)
                    {
                        if (i == input[0] - 1)
                        {
                            mapp[i, j] = mapp[i - 1, j];
                        }
                        else
                        {
                            mapp[i, j] = mapp[i + 1, j];
                        }
                    }
                }
            }
            for (int i = 0; i < input[0]; i++)
            {
                for (int j = 0; j < input[1]; j++)
                {
                    Console.Write(mapp[i, j] + " ");
                }
                Console.WriteLine();
            }
        }*/
        //146A
        /*static void Main()
        {
            string S = Console.ReadLine();
            switch (S)
            {
                case "SUN":
                    Console.WriteLine(7);
                        break;
                case "MON":
                    Console.WriteLine(6);
                    break;
                case "TUE":
                    Console.WriteLine(5);
                    break;
                case "WED":
                    Console.WriteLine(4);
                    break;
                case "THU":
                    Console.WriteLine(3);
                    break;
                case "FRI":
                    Console.WriteLine(2);
                    break;
                case "SAT":
                    Console.WriteLine(1);
                    break;

            }
        }*/
        //146B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            List<string> ans = new List<string>();
            for (int i = 0;i < S.Length;i++)
            {
                var tempch = change(S[i],N);
                ans.Add(tempch.ToString());
            }
            foreach (string a in ans)
            {
                Console.Write(a);
            }
            Console.WriteLine();
        }
        static char change(char temp,int n)
        {
            string al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
            int num = al.IndexOf(temp) + n;
            if (num >= 26)
            {
                num = num - 26;
                var ans1 = al[num];
                return ans1;
            }
            else
            {
                var ans2 = al[num];
                return ans2;
            }
            //var ans = al[al.IndexOf(temp) + n];
        }*/
        //146C難しい
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long A = input[0];
            long B = input[1];
            long X = input[2];
            //var x = mm(N);
            var ans = mm2(A, B,X);
            //var ans = function(A, B, X);
            if (ans <= 0)
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(ans);
            }
        }
        static long mm2(long a,long b,long Xor)
        {
            var l = 1;
            var r = (int)1e9;
            long ans = 0;
            while (l <= r)
            {
                var n = (r + l) / 2;
                var val = a * n + n.ToString().Length * b;
                if (Xor - val >= 0)
                {
                    ans = n;
                    l = n + 1;
                }
                else
                {
                    r = n - 1;
                }
            }
            return ans;
        }*/
        //145C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<int[]> inputdata = new List<int[]>();
            for (int i= 0;i < N;i++)
            {
                int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
                inputdata.Add(input);
            }

        }*/
        //ABC145A
        /*static void Main()
        {
            int r = int.Parse(Console.ReadLine());
            var ans = Math.Pow(r, 2);
            Console.WriteLine(ans);
        }*/
        //ABC145B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            bool flag = false;
            List<string> cAns = new List<string>();
            List<string> cAns2 = new List<string>();
            if (S.Length % 2 == 1)
            {
                Console.WriteLine("No");
            }
            else
            {
                for (int i = 0; i < S.Length / 2; i++)
                {
                    cAns.Add(S[i].ToString());
                    cAns2.Add(S[i + (S.Length / 2)].ToString());
                }
                for (int i = 0; i < S.Length / 2; i++)
                {
                    if (cAns[i] != cAns2[i])
                    {
                        flag = true;
                    }
                }
                if (flag)
                {
                    Console.WriteLine("No");
                }
                else
                {
                    Console.WriteLine("Yes");
                }
            }
        }*/
        //147A
        /*static void Main()
        {
            int ans = 0;
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i =0;i < input.Length;i++)
            {
                ans += input[i];
            }
            if (ans >= 22)
            {
                Console.WriteLine("bust");
            }
            else
            {
                Console.WriteLine("win");
            }
        }*/
        //147B
        /*static void Main()
        {
            string S = Console.ReadLine();
            List<string> A = new List<string>();
            List<string> B = new List<string>();
            List<string> C = new List<string>();
            if (S.Length % 2 == 0)
            {
                for (int i = 0; i < S.Length / 2; i++)
                {
                    A.Add(S[i].ToString());
                    B.Add(S[i + (S.Length / 2)].ToString());
                }
                for (int i = B.Count - 1; i >= 0; i--)
                {
                    C.Add(B[i]);
                }
                int hug = 0;
                for (int i = 0; i < S.Length / 2; i++)
                {
                    //Console.WriteLine(A[i] + " + "+ C[i]);
                    if (A[i] == C[i])
                    {
                        hug++;
                    }
                }
                Console.WriteLine(S.Length / 2 - hug);
            }
            else
            {
                for (int i = 0; i < S.Length / 2; i++)
                {
                    A.Add(S[i].ToString());
                    B.Add(S[i + (S.Length / 2) + 1].ToString());
                }
                for (int i = B.Count - 1; i >= 0; i--)
                {
                    C.Add(B[i]);
                }
                int hug = 0;
                for (int i = 0; i < S.Length / 2; i++)
                {
                    //Console.WriteLine(A[i] + " + "+ C[i]);
                    if (A[i] == C[i])
                    {
                        hug++;
                    }
                }
                Console.WriteLine(S.Length / 2 - hug);
            }
        }*/
        //147C
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            long[] A = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long Answer = 0;
            for (int i = 0; i < N-1;i++)
            {
                for (int j = i+1;j < N;j++)
                {
                    
                    Answer += xor(A[i] , A[j] );
                }
            }
            Answer = Answer % 1000000007;
            Console.WriteLine(Answer);
        }
        static long xor(long a, long b)
        {
            string A = Convert.ToString(a, 2);
            string B = Convert.ToString(b, 2);
            if (A.Length > B.Length)
            {
                B = B.PadLeft(A.Length, '0');
            }
            else if (B.Length > A.Length)
            {
                //var cnt2 = B.Length - A.Length;
                A = A.PadLeft(B.Length, '0');
                //Console.WriteLine(A.PadLeft(B.Length,'0'));
            }
            string an = "";
            for (int i = 0;i < A.Length;i++)
            {
                if (A[i] == B[i])
                {
                    an += 0.ToString();
                }
                else
                {
                    an += 1.ToString();
                }
            }
            long C = Convert.ToInt64(an, 2);
            return C;
        }*/
        //147C
        /*static void Main()
        {
            int n = 3;
            for (int bit = 0;bit < (1<<n);++bit)
            {
                List<int> S;
                for (int i = 0;i < n;++i)
                {
                    if ((bit & (1<<i)) > 0)
                    {

                    }
                }
            }
        }*/
        //149A
        /*static void Main()
        {
            string[] str = Console.ReadLine().Split();
            string ans = str[1] + str[0];
            Console.WriteLine(ans);
        }*/
        //149B
        /*static void Main()
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long takahashi = input[0];
            long aoki = input[1];
            long K = input[2];

            if (takahashi - K > 0)
            {
                Console.WriteLine(takahashi - K + " " + aoki);
            }
            else
            {
                if (aoki - (Math.Abs(takahashi - K)) > 0)
                {
                    Console.WriteLine(0 + " " + (aoki - (Math.Abs(takahashi - K))));
                }
                else
                {
                    Console.WriteLine(0 + " " +0);
                }
            }
        }*/
        //149C
        /*static void Main()
        {
            int isprime = int.Parse(Console.ReadLine());
            bool ans = false;
            while (true)
            {
                if (Isprime(isprime))
                {
                    ans = true;
                }
                if (ans)
                {
                    break;
                }
                isprime++;     
            }
            Console.WriteLine(isprime);
        }
        static bool Isprime(int num)
        {
            if (num < 2)
            {
                return false;
            }
            else if (num == 2)
            {
                return true;
            }
            else if (num %2 == 0)
            {
                return false;
            }
            double sqrtnum = Math.Sqrt(num);
            for (int i = 3;i <= sqrtnum;i +=2)
            {
                if ( num % i == 0)
                {
                    return false;
                }
            }
            return true;
        }*/
        //148A
        /*static void Main()
        {
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());
            Console.WriteLine(6 - A - B);
        }*/
        //148B
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split();
            string S = input[0];
            string T = input[1];
            char[] ans = new char[N * 2];
            ans[0] = S[0];
            for (int i = 0;i < N*2;i++)
            {

            }
        }*/
        //ドワンゴからの挑戦状
        /*static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            List<Data> datalist = new List<Data>();
            for (int i = 0;i < N;i++)
            {
                var temp = Console.ReadLine().Split();
                Data data = new Data();
                data.str = temp[0];
                data.integer = int.Parse(temp[1]);
                datalist.Add(data);
            }
            string keyword = Console.ReadLine();

        }
    }
    class Data
    {
        public string str { get; set; }
        public int integer { get; set; }
    }*/
        //152A
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            if (N == M)
            {
                Console.WriteLine("Yes");

            }
            else
            {
                Console.WriteLine("No");
            }
        }*/
        //152B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = input[0];
            int b = input[1];
            string Ansa = "";
            string Ansb = "";
            for (int i = 0; i < b;i++)
            {
                Ansa += a;
            }
            for (int i = 0;i < a;i++)
            {
                Ansb += b;
            }
            if (Ansa.CompareTo(Ansb) == -1)
            {
                Console.WriteLine(Ansa);
            }
            else if (Ansa.CompareTo(Ansb) == 0)
            {
                Console.WriteLine(Ansa);
            }
            else
            {
                Console.WriteLine(Ansb);
            }
        }*/
        //152C
        /*static void Main()
        {
            long N = long.Parse(Console.ReadLine());
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            List<long> temp = new List<long>();
            long ans = 0;
            for (int i = 0;i < N;i++)
            {
                temp.Add(input[i]);
            }
            Console.WriteLine(ans);
        }*/

        /*static public void Main()
        {

            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var w = input[0];
            var h = input[1];
            var bmi = input[2];
            double Answer = 0;

            double temp = 10000 * w / h / h;

            if (temp > bmi)
            {
                double hh = (bmi * h * h) / 10000;
                Answer = Math.Ceiling(hh);
                Console.WriteLine(w - Answer);
            }
            else
            {
                Console.WriteLine(Answer);
            }
        }*/

        //159A
        /*static void Main() 
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = input[0];
            var M = input[1];
            long Ans = kaijo(N) + kaijo(M);
            Console.WriteLine(Ans);

        }
        static long kaijo(int num) {
            long ans = 1;
            for (int i = num;i > num-2;i--)
            {
                ans *= i;
            }
            long Answer = 0;
            Answer = ans / 2;
            return Answer;
        }*/
        //159B
        /*static void Main()
        {
            string input = Console.ReadLine();
            string A = "";
            string B = "";
            for (int i = 0; i <  ( input.Length - 1 ) / 2; i++)
            {
                A += input[i];
            }
            for (int i = (input.Length + 3) / 2 -1; i < input.Length; i++)
            {
                B += input[i];
            }
            if (A.Equals(B))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }*/
        //159C
        /*static void Main()
        {
            double L = double.Parse(Console.ReadLine());
            double ans = L / 3;
            double Ans = ans * ans * ans;
            Console.WriteLine(Ans);
            //in430 out2944703.703703703824
        }*/
        //159D
        //static void Main()
        //{
        /*long N = long.Parse(Console.ReadLine());
        List<long> input = new List<long>();
        for (long i = 0; i < N; i++)
        {
            input.Add(long.Parse(Console.ReadLine()));
        }
        for (int i = 0; i < input.Count; i++)
        {
            List<long> temp = new List<long>();
            for (int j = 0; j < input.Count;j ++)
            {
                if (i != j)
                {
                    temp.Add(input[j]);
                }
            }

        }*/
        /*long N = long.Parse(Console.ReadLine());
        long[] As = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long[] f = new long[200001];
        long[] c1 = new long[200001];
        long[] c2 = new long[200001];
        for (int i = 0;i < N;i++)
        {
            f[As[i]]++;
        }
        for (long i = 0;i <= N; i++)
        {
            if (f[i] > 1)
            {
                c1[i] += f[i] * (f[i] - 1) / 2;
            }
        }
        for (int i = 0;i < N; i++)
        {
            if (f[i]-1 > 1)
            {
                c2[i] = c1[i] - 1; 
            }
        }
        for (int i = 0;i < N;i++)
        {
            var ans = c1[As[i]] - c2[As[i]];
            Console.WriteLine(ans);
        }*/
        /*for (int i = 0;i < input.Length;i++)
        {
            List<long> templist = new List<long>();
            for (int j = 0; j < input.Length; j++)
            {
                if (i != j)
                {
                    templist.Add(input[j]);
                }
            }
            var ansList = templist
                .GroupBy(x => x)
                .Where(x => x.Count() > 0)
                .Select(x => new { typecount = x.Count() })
                .ToList();
            var ans = 0;
            foreach (var A in ansList) {
                ans += A.typecount * (A.typecount - 1) / 2;
            }
            Console.WriteLine(ans);
        }*/
        /*List<int> dataList = new List<int>() { 2, 1, 2, 1, 3 };
        var duplicationList = dataList
            .GroupBy((int x) => x)
            .Where(x => x.Count() > 1)
            .Select(g => new { number = g.Key, duplicationCount = g.Count() - 1 })
            .ToList();
        foreach (var num in duplicationList)
        {
            Console.WriteLine(num);
        }
        string temo = duplicationList.GetEnumerator().ToString();
        Console.WriteLine(temo);*/
        /*}
        static long func1(long num)
        {
            var ans = num * (num - 1) / 2;
            return ans;
        }*/
        //160A
        /*static void Main()
        {
            string str = Console.ReadLine();
            if (str[2].Equals(str[3]) && str[4].Equals(str[5]))
            {
                Console.WriteLine("Yes");
            }
            else { Console.WriteLine("No"); }
        }*/
        //160B
        static void Main()
        {
            long coin = long.Parse(Console.ReadLine());
            long ple = 0;
            long Ans = 0;
            long[] list = new long[6]{ 500, 100, 50, 10 ,5, 1 };
            /*for (int i = 0; i< list.Length;i++) {
                ple = coin / list[i];
                if (list[i] == 500 && list[i] == 5)
                {
                    if (list[i] == 500)
                    {
                        Ans += 1000 * ple;
                    }
                    else
                    {
                        Ans += 5 * ple;
                    }
                }
                coin = coin - ple * list[i];
            }*/
            ple = coin / 500;
            Ans += ple * 1000;
            coin = coin - 500 * ple;
            ple = coin / 5;
            Ans += ple * 5;
            Console.WriteLine(Ans);
        }
    }
    /*class Data
    {
        public int a { get; set; }
        public int b { get; set; }
    }*/
}

//125C難しい
/*namespace CSharp
{
    class Program
    {
        static IEnumerable<long> EnumerateDivisors(long n)
        {
            for (long i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    yield return i;
                    if (n / i != i)
                    {
                        yield return n / i;
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            ReadString();
            long[] A = ReadLongArray();

            long[] divisors = Enumerable.Concat(EnumerateDivisors(A[0]), EnumerateDivisors(A[1]))
                                        .Distinct().ToArray();
            long ans = divisors.Select(x => new { Value = x, Count = A.Count(v => v % x == 0) })
                               .Where(x => x.Count >= A.Length - 1)
                               .OrderByDescending(x => x.Value)
                               .First().Value;
            Console.WriteLine(ans);
        }

        #region Helpers

        static int[] ReadIntArray() => Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        static long[] ReadLongArray() => Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

        static int[] ReadLineIntArray(int count) => Enumerable.Repeat(0, count).Select(_ => int.Parse(Console.ReadLine())).ToArray();
        static long[] ReadLineLongArray(int count) => Enumerable.Repeat(0, count).Select(_ => long.Parse(Console.ReadLine())).ToArray();

        static string ReadString() => Console.ReadLine();
        static int ReadInt() => int.Parse(Console.ReadLine());
        static long ReadLong() => long.Parse(Console.ReadLine());

        static void ReadInt(out int first)
        {
            var array = ReadIntArray();
            first = array[0];
        }

        static void ReadInt(out int first, out int second)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
        }

        static void ReadInt(out int first, out int second, out int third)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadInt(out int first, out int second, out int third, out int fourth)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        static void ReadLong(out long first)
        {
            var array = ReadLongArray();
            first = array[0];
        }

        static void ReadLong(out long first, out long second)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
        }

        static void ReadLong(out long first, out long second, out long third)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadLong(out long first, out long second, out long third, out long fourth)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        #endregion
    }
}*/


Measured memory_bytes: 11220