#include <iostream>
#include <fstream>

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

int n, G, p[5005], gr[5005], DP[5005][10000];

int main()
{
    f>>n>>G;
    for(int i = 1; i <= n; i++)
        f>>gr[i]>>p[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= G; j++)
        {
            DP[1][j] = DP[0][j];
            if(gr[i] <= j)
            {
                DP[1][j] = max(DP[1][j],DP[0][j-gr[i]]+p[i]);
                //cout<<DP[i][j]<<' '<<DP[i-1][j-gr[i]]+p[i]<<' '<<i<< ' '<<j<< '\n';
            }
        }
        for(int j = 1; j <= G; j++) DP[0][j] = DP[1][j];
    }
    /*for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= G; j++)
        {
            cout<<DP[i][j]<< ' ';
        }
        cout<<'\n';
    }*/
    g<<DP[1][G]<<'\n';
    return 0;
}