#include <fstream>

using namespace std;

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

int n, gr[5004], c[5004], cmax[3][10001], 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, G, lin=0;
    for(i=n;i>0;i--)
    {
        for(G=0;G<=GMAX;G++)
        {
            cmax[lin][G]=cmax[1-lin][G];
            if(gr[i]<=G&&c[i]+cmax[1-lin][G-gr[i]]>cmax[lin][G])
                cmax[lin][G]=c[i]+cmax[1-lin][G-gr[i]];
        }
        lin=1-lin;
    }
}

void afisare()
{
    fout<<cmax[1][GMAX]<<'\n';
}