#include <stdio.h>
#include <stdlib.h>
int m[2][10001],v[2][5000];
int main()
{
    FILE *fin,*fout;
    int n,g,i,j;
    fin=fopen("rucsac.in","r");
    fscanf(fin,"%d%d",&n,&g);
    for(i=0;i<n;i++){
        fscanf(fin,"%d%d",&v[0][i],&v[1][i]);
    }
    fclose(fin);
    for(i=0;i<n;i++){
        for(j=1;j<=g;j++){
            if((j>=v[0][i])&&(m[i%2][j]<(m[i%2][j-v[0][i]]+v[1][i]))){
                m[(i%2+1)%2][j]=m[i%2][j-v[0][i]]+v[1][i];
            }else{
                m[(i%2+1)%2][j]=m[i%2][j];
            }
        }
    }
    fout=fopen("rucsac.out","w");
    fprintf(fout,"%d",m[n%2][g]);
    fclose(fout);
    return 0;
}