using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

static class MainClass
{
    private static Scanner scanner;
    public static void Main()
    {
        scanner = new Scanner();
        Solve();
        // for scanner bug
        scanner.Next();
    }

    private static void Solve()
    {
        var N = scanner.NextInt();
        var W = scanner.NextInt();
        var dp = new int[N + 10, W + 10];
        var items = new List<Tuple<int, int>>();
        for (int i = 0; i < N; i++)
        {
            var v = scanner.NextInt();
            var w = scanner.NextInt();
            items.Add(Tuple.Create(v, w));
        // dp[i,j] = value, weight is j when i items selected or not-selected.
        // dp[i + 1,j] = max(dp[i,j],dp[i, j - w_i] + v_i) if j - w_i >= 0, dp[i,j]
        }
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j <= W; j++)
            {
                if (j - items[i].Item2 >= 0)
                {
                    dp[i + 1, j] = Max(dp[i, j], dp[i, j - items[i].Item2] + items[i].Item1);
                }
                else
                {
                    dp[i + 1, j] = dp[i, j];
                }
            }
        }
        var maxes = 0;
        for (int i = 0; i <= W; i++)
        {
            maxes = Max(dp[N, i], maxes);
        }
        Console.WriteLine(maxes);
    }

    private static int UpperBound<T>(this IEnumerable<T> list, T item) where T : IComparable<T> => UpperBound(list.ToList(), item);
    private static int LowerBound<T>(this IEnumerable<T> list, T item) where T : IComparable<T> => LowerBound(list.ToList(), item);

    private static int UpperBound<T>(this List<T> list, T item) where T : IComparable<T>
    {
        return list.BinarySearch(item, -1, list.Count, (first, second) => first.CompareTo(second) > 0);
    }

    private static int LowerBound<T>(this List<T> list, T item) where T : IComparable<T>
    {
        return list.BinarySearch(item, -1, list.Count, (first, second) => first.CompareTo(second) >= 0);
    }

    private static int BinarySearch<T>(this List<T> list, T item, int left, int right, Func<T, T, bool> isOkPredicate)
    {
        while (Math.Abs(right - left) > 1)
        {
            var mid = left + (right - left) / 2;
            if (isOkPredicate(list[mid], item))
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        return right;
    }


    #region ライブラリ

    public static long ToInt64(this string str) => long.Parse(str);
    public static bool IsInt32(this string str)
    {
        var o = 0;
        return int.TryParse(str, out o);
    }
    public static int ToInt32(this string str) => str == "" ? 0 : int.Parse(str);
    public static double ToDouble(this string str) => double.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<long> SplittedStringToInt64List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 4;
    public const long LONGINF = long.MaxValue / 2;
    public const int Mod1e9 = 1000000007;
    public static List<int> ToCumulativeSumList(this List<int> list)
    {
        var ls = new List<int>
        {
            list[0]
        };
        var count = list.Count;
        for (int i = 1; i < count; i++)
        {
            ls.Add(list[i] + ls.Last());
        }
        return ls;
    }

    public static void PrintArray(long[,] array)
    {
        for (int i = 0; i < array.GetLength(0); i++)
        {
            var sb = new StringBuilder();
            for (int j = 0; j < array.GetLength(1); j++)
            {
                sb.Append(array[i, j]).Append(" ");
            }
            Console.WriteLine(sb.ToString().Trim());
        }
    }
    public static int Manhattan(int x1, int x2, int y1, int y2)
    {
        return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
    }

    public static int Manhattan(KeyValuePair<int, int> keyValuePair1, KeyValuePair<int, int> keyValuePair2)
    {
        return Manhattan(keyValuePair1.Key, keyValuePair2.Key, keyValuePair1.Value, keyValuePair2.Value);
    }

    public static T DeepClone<T>(this T src)
    {
        var memoryStream = new MemoryStream();
        var binaryFormatter = new BinaryFormatter();
        binaryFormatter.Serialize(memoryStream, src);
        memoryStream.Seek(0, SeekOrigin.Begin);
        memoryStream.Dispose();

        return (T)binaryFormatter.Deserialize(memoryStream);
    }

    public static Dictionary<T, int> ToCountedDictionary<T>(this IEnumerable<T> items)
    {
        var dic = new Dictionary<T, int>();
        foreach (var item in items)
        {
            if (dic.ContainsKey(item))
                dic[item]++;
            else
                dic.Add(item, 1);
        }
        return dic;
    }
    public static Dictionary<TKey, TValue> KeyValuePairListToDictionary<TKey, TValue>(this IEnumerable<KeyValuePair<TKey, TValue>> pairs)
    {
        var dic = new Dictionary<TKey, TValue>();
        foreach (var item in pairs)
        {
            dic.Add(item.Key, item.Value);
        }
        return dic;
    }
    public class Scanner
    {
        private readonly TextReader reader;
        public Scanner()
        {
            reader = Console.In;
        }
        public Scanner(TextReader reader)
        {
            this.reader = reader;
        }
        private string NextWord()
        {
            var sb = new StringBuilder();
            while (true)
            {
                var c = reader.Read();
                if ((c == 13 || c == 10 || c == 32) && sb.Length > 0 || c == -1)
                {
                    break;
                }
                sb.Append((char)c);
            }
            return sb.ToString().Trim();
        }
        public int NextInt() => NextWord().ToInt32();
        public string Next() => NextWord();
        public double NextDouble() => NextWord().ToDouble();
        public long NextLong() => NextWord().ToInt64();
        public BigInteger NextBigInteger() => NextWord().ToBigInteger();
        public string NextLine()
        {
            var str = reader.ReadLine();
            if (string.IsNullOrWhiteSpace(str))
            {
                return reader.ReadLine();
            }
            else
            {
                return str;
            }
        }
        private List<string> NextLineToList() => NextLine().Split(new char[] { ' ' },
                                                                  StringSplitOptions.RemoveEmptyEntries)
                                                           .ToList();
        public List<int> NextLineToIntList() => NextLineToList().Select(x => int.Parse(x))
                                                                .ToList();
    }
    public static long Sums(IEnumerable<int> list)
    {
        var sum = 0L;
        foreach (var item in list)
        {
            sum += Math.Abs(item);
        }
        return sum;
    }
    public static string IEnumerableListToString<T>(this IEnumerable<T> ls, bool withSpace = false)
    {
        var sb = new StringBuilder();
        foreach (var item in ls)
        {
            sb.Append(item);
            if (withSpace)
            {
                sb.Append(" ");
            }
        }
        return sb.ToString();
    }
    #endregion

    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, 1, -1 };

    public static int[] dxx = { 0, 1, 1, 1, 0, -1, -1, -1 };
    public static int[] dyy = { 1, 1, 0, -1, -1, -1, 0, 1 };

}




Measured memory_bytes: 19824