#include <iostream>
#include <cstdio>

using namespace std;

int castig[2][10001],gr[10001],c[5001],i,j,n,g,obiect,l=0;

int main()
{
    FILE *fin=fopen("rucsac.in","r"),
        *fout=fopen("rucsac.out","w");
    fscanf(fin,"%d %d ",&n,&g);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d %d ",&gr[i],&c[i]);
    for(i=1;i<=n;i++,l=1-l)
        for(j=0;j<=g;j++)
        {
            castig[1-l][j]=castig[l][j];
            if(gr[i]<=j && castig[l][j-gr[i]]+c[i]>castig[1-l][j])
                castig[1-l][j]=castig[l][j-gr[i]]+c[i];
        }
    i=n;
    j=g;
    fprintf(fout,"%d \n",castig[l][j]);
    return 0;
}