using static System.Math;
using System.Collections.Generic;
using System.Linq;
using System;

public class Hello
{
    static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var wmax = int.Parse(line[1]);
        var vaL = new int[n + 1];
        var w = new int[n + 1];
        var dp = new int[n + 1, wmax + 1];
        SetData(n, vaL, w);
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= wmax; j++)
            {
                if (j < w[i]) dp[i + 1, j] = dp[i, j];
                else dp[i + 1, j] = Max(dp[i, j], dp[i, j - w[i]] + vaL[i]);
            }
        Console.WriteLine(dp[n, wmax]);
    }
    public static void SetData(int n, int[] vaL, int[] w)
    {
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            w[i] = int.Parse(line[0]);
            vaL[i] = int.Parse(line[1]);
        }
    }
}