#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream fout("rucsac.out");
int n,g,w[5002],p[5002],d[3][10002],l;
int main()

{
    int i,j;
    f>>n>>g;
    for(i=1;i<=n;i++) f>>w[i]>>p[i];
    d[1][w[1]]=p[1];
    l=0;
    for(i=1;i<=n;i++,l=1-l)
        for(j=1;j<=g;j++)
            if(w[i]<=j)
            {
                d[1-l][j]=d[l][j];
                d[1-l][j]=max(d[l][j],d[l][j-w[i]]+p[i]);
            }
    fout<<d[l][g]<<'\n';
    f.close();
    fout.close();
    return 0;
}