#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gmax;
int gr[5001],p[5001],cmax[3][5001],uz[5001][5001],col;

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

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

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

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

void afisare()
{
    /*int sol,i;
    sol=cmax[1][1];
    for(i=2;i<=n;i++)
        if(sol<cmax[1][i])
            sol=cmax[1][i];
    fout<<sol;*/
    fout<<cmax[1][gmax];
}