#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int D[10000][10000],N,G,W[90000],P[90000];
void citire ()
{
    fin>>N>>G;
    for(int i=1; i<=N; i++)
        fin>>W[i]>>P[i];
}
void rezolvare ()
{
    for(int i=1; i<=N; i++)
        for(int j=0; j<=G; j++)
        {
            if(j-W[i]>=0)
                D[i][j]=max(D[i-1][j],D[i-1][j-W[i]]+P[i]);
            else
                D[i][j]=D[i-1][j];
            delete D[i-1];
        }

}
int main()
{
    citire();
    rezolvare();
    fout<<D[N][G];
}