#include <cstdio>
#include <algorithm>
#define MAXN 5010
#define MAXG 10010

using namespace std;
FILE *fin=fopen("rucsac.in","r"),*fout=fopen("rucsac.out","w");
int g[MAXN],p[MAXN],d[2][MAXG];
int main(){
    int n,G;
    fscanf(fin,"%d%d",&n,&G);
    for(int i=1;i<=n;i++){
        fscanf(fin,"%d%d",&g[i],&p[i]);
    }
    int lin=0;
    for(int i=1;i<=n;i++,lin=1-lin){
        for(int cg=0;cg<=G;cg++){
            d[1-lin][cg]=d[lin][cg];

            if(g[i]<=cg){
                d[1-lin][cg]=max(d[1-lin][cg],d[lin][cg-g[i]]+p[i]);
            }
        }
    }
    fprintf(fout,"%d",d[lin][G]);
    return 0;
}