#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int w[5005], p[5005], dp[3][10005], n, gmax;

int main()
{
    f >> n >> gmax;
    for(int i = 1; i <= n; ++i)
        f >> w[i] >> p[i];
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= gmax; ++j)
        {
            if(w[i] <= j)
                dp[2][j] = max(dp[1][j], dp[1][j - w[i]] + p[i]);
            else dp[2][j] = dp[1][j];
        }
        for(int j = 1; j <= gmax; ++j)
            dp[1][j] = dp[2][j];
    }
    g << dp[1][gmax] << '\n';

}