#include <fstream>
#include <algorithm>
using namespace std;

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

int n, gmax, maxim;
int g[5010], c[5010];
int cmax[2][10010];


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>>g[i]>>c[i];
}
void pd()
{
    //linia l va fi cea pe care avem solutia pentru al (i-1)-lea element,iar pe linia 1-l vom construi solutia pentru elementul i.
    int l=0,ind,i;
    for(i=1;i<=n;i++)
    {
        for(ind=0;ind<=gmax;ind++)
        {
            cmax[1-l][ind]=cmax[l][ind];

            if(g[i]<=ind)
                cmax[1-l][ind]=max(cmax[1-l][ind],cmax[l][ind-g[i]]+c[i]);
        }
        l=1-l;
    }
    maxim=cmax[l][gmax];

}
void afisare()
{
   fout<<maxim<<'\n';
   fout.close();
}