#include <iostream>
#include <fstream>

using namespace std;

int n,G,W,P;
int d[2][10002];

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>G;
    for(int i=1;i<=n;i++)
    {
        f>>W>>P;

        for(int j=0;j<=G;j++)
        {
            d[1][j]=d[0][j];
            if(W<=j)
                d[1][j]=max(d[1][j],d[0][j-W]+P);
        }

        for(int j=0;j<=G;j++)
            d[0][j]=d[1][j];
    }
    g<<d[1][G]<<'\n';
    f.close();
    g.close();
    return 0;
}