You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 100
* 1 ≤ wi ≤ 10,000,000
* 1 ≤ W ≤ 1,000,000,000

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9
using System;
using System.Linq;

namespace DPL1_F
{
    class Program
    {
        static int W;
        static int n;
        static int[] w = new int[200];
        static int[] v = new int[200];
        const int MAX = 200000;
        const long INF = (long)1 << 40;
        static void Main(string[] args)
        {
            solve();
        }
        static void solve()
        {
            var t = scan;
            n = t[0];
            W = t[1];
            int data = 2;
            for (int i = 0; i < n; i++)
            {
                var j = scan;
                w[i] = j[1];
                v[i] = j[0];
                if (j[1] > 1000) data = 3;
                if (j[0] > 1000) data = 2;
            }
            if (n <= 30) data = 1;
            if (data == 1) data1();
            if (data == 2) data2();
            if (data == 3) data3();
        }
        static void data1()
        {
            int n1 = n / 2;
            var ps = new pair<long, long>[1 << n1];
            for (int i = 0; i < 1 << n1; i++)
            {
                long sw = 0, sv = 0;
                for (int j = 0; j < n1; j++)
                {
                    if ((i >> j & 1) == 1)
                    {
                        sw += w[j];
                        sv += v[j];
                    }
                }
                ps[i] = new pair<long, long>(sw, sv);
            }
            Array.Sort(ps);
            int m = 1;
            for (int i = 0; i < 1 << n1; i++)
            {
                if (ps[m - 1].Second < ps[i].Second) ps[m++] = ps[i];
            }
            ps = ps.Take(m).ToArray();

            long res = 0;
            int n2 = n - n1;

            for (int i = 0; i < 1 << n2; i++)
            {
                long sw = 0, sv = 0;
                for (int j = 0; j < n2; j++)
                {
                    if ((i >> j & 1) == 1)
                    {
                        sw += w[n1 + j];
                        sv += v[n1 + j];
                    }
                }
                if (sw <= W)
                {
                    long tv = ps[UpperBound1(ps, W - (int)sw) - 1].Second;
                    res = Math.Max(res, sv + tv);
                }
            }
            Console.WriteLine(res);
        }
        static void data2()
        {
            var dp = new long[W + 1];
            for (int i = 0; i < n; i++)
            {
                for (int j = W; j >= w[i]; j--)
                {
                    dp[j] = Math.Max(dp[j], dp[j - w[i]] + v[i]);
                }
            }
            Console.WriteLine(dp[W]);
        }
        static void data3()
        {
            var dp = Enumerable.Repeat(INF, MAX + 1).ToArray();
            dp[0] = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = MAX; j >= 1; j--)
                {
                    if (v[i] > j) dp[j] = Math.Min(dp[j], w[i]);
                    else dp[j] = Math.Min(dp[j], dp[j - v[i]] + w[i]);
                }
            }
            if (dp[MAX] < W) Console.WriteLine(MAX);
            else
            {
                /*for (int i = 0; i < MAX+1; i++)
                {
                    if (dp[i] > W)
                    {
                        Console.WriteLine(i-1);
                        break;
                    }
                }*/
                Console.WriteLine(UpperBound3(dp, W) - 1);
            }
        }

        static int UpperBound3(long[] arr, int val)
        {
            int low = 0, high = arr.Count();
            int mid;

            while (low < high)
            {
                mid = ((high - low) >> 1) + low;
                if (arr[mid] <= val) low = mid + 1;
                else high = mid;
            }
            return low;
        }
        static int UpperBound1(pair<long, long>[] arr, int val)
        {
            int low = 0, high = arr.Count();
            int mid;

            while (low < high)
            {
                mid = ((high - low) >> 1) + low;
                if (arr[mid].First <= val) low = mid + 1;
                else high = mid;
            }
            return low;
        }
        static int[] scan { get { return Array.ConvertAll(Console.ReadLine().Split(), int.Parse); } }
    }

    public class pair<T, U> : IComparable where T : IComparable<T>
    {
        public pair()
        {
        }

        public pair(T first, U second)
        {
            this.First = first;
            this.Second = second;
        }

        public int CompareTo(Object obj)
        {
            pair<T, U> cast = (pair<T, U>)obj;
            return First.CompareTo(cast.First);
        }

        public T First { get; set; }

        public U Second { get; set; }

        public override string ToString()
        {
            return string.Format("{0} {1}?\n", First, Second);
        }
       
    }
}