#include <stdio.h>

#define N_MAX 5000

int v[3][N_MAX+2];

int main()
{
    FILE *fin,*fout;
    int i,n,g,w,p,j;
    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",&w,&p);
        for(j=1;j<=g;j++){
            if(j>=w){
                if(v[1][j]-p>v[1][j-w])
                    v[2][j]=v[1][j];
                else
                    v[2][j]=v[1][j-w]+p;
            }
            else
                v[2][j]=v[1][j];
        }
        for(j=1;j<=g;j++)
            v[1][j]=v[2][j];
    }
    fprintf(fout,"%d\n",v[2][g]);
    fclose(fin);
    fclose(fout);
    return 0;
}