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

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int g[2][10005],N,G;

int main()
{
    fin>>N>>G;
    int i,j,p,w;
    for(i=1;i<=N;i++)
        {
            fin>>w>>p;
            for(j=G;j>=w;j--)
                g[1][j]=max(g[0][j],g[0][j-w]+p);
            swap(g[0],g[1]);
        }
    fout<<g[0][G];
}