#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct obiect
{
    int g,p;
}v[5001];

int cmax[5001];
int n,G,gmax;

void citire()
{
    int i;
    f>>n>>G;
    for (i=1;i<=n;i++)
        f>>v[i].g>>v[i].p;
}

void afis ()
{
    int i,sol;
    sol=0;
    for(i=0;i<=G;i++)
        if(sol<cmax[i])
            sol=cmax[i];
    g<<sol;
}

void dinamica()
{
    int i,j;
    cmax[0]=0;
    for (i=1;i<=n;i++){

        for (j=gmax;j>=0;j--){
            if(cmax[j+v[i].g]<cmax[j]+v[i].p && j+v[i].g<=G && (!j || cmax[j]) ){
                cmax[j+v[i].g]=cmax[j]+v[i].p;
                if(v[i].g+j>gmax)
                    gmax=v[i].g+j;
            }
        }
    }
    afis();
}

int main()
{
    citire();
    dinamica();
}