#include <fstream>

using namespace std;

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

int n, gr[5001], c[5001], cmax[5001], uz[10001][5001], G, GMAX;

void citire();
void pd();
void afisare();

int main()
{
    citire();
    pd();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>GMAX;
    for(i=1;i<=n;i++) fin>>gr[i]>>c[i];
}

void pd()
{
    int i, j;
    for(G=1;G<=GMAX;G++)
        for(i=1;i<=n;i++)
            if(gr[i]<=G&&uz[G-gr[i]][i]==0)
                if(c[i]+cmax[G-gr[i]]>cmax[G])
                {
                    cmax[G]=c[i]+cmax[G-gr[i]];
                    for(j=1;j<=n;j++)
                        uz[G][j]=uz[G-gr[i]][j];
                    uz[G][i]=1;
                }
}

void afisare()
{
    int i;
    fout<<cmax[GMAX]<<'\n';
    //for(i=1;i<=n;i++)
        //if(uz[GMAX][i]) fout<<i<<' ';
}