#include<cstdio>
#define MM 5010
using namespace std;
FILE *in,*out;

int gr[MM],pr[MM],var[MM*3];

inline int maxim(int a, int b){
    return a > b ? a : b;
}

int main(){
    in=fopen("rucsac.in","r");
    out=fopen("rucsac.out","w");

    int n,G,sol=-1;
    fscanf(in,"%d%d",&n,&G);
    for(int i=1;i<=n;i++)
        fscanf(in,"%d%d",&gr[i],&pr[i]);
    for(int i=1;i<=n;i++)
        for(int j=G-gr[i];j>=0;j--){
            var[gr[i]+j]=maxim(var[gr[i]+j], var[j]+pr[i]);
            sol=maxim(sol,var[gr[i]+j]);
        }

    fprintf(out,"%d",sol);
    fclose(in);
    fclose(out);
    return 0;
}