#include <fstream>
#define NMAX 5002
#define GMAX 10002

using namespace std;

int n, G, lc=1, lp=0;
int g[NMAX], c[NMAX];
int cmax[2][GMAX];

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

void citire();
void pd();

int main(){
    citire();
    pd();
    fout << cmax[lp][G] << '\n';
    fout.close();
    return 0;
}

void citire(){
    int i;
    fin >> n >> G;
    for(i=1; i<=n; i++)
        fin >> g[i] >> c[i];
}

void pd(){
    int i, x;
    for(i=1; i<=n; i++){
        for(x=1; x<=G; x++){
            cmax[lc][x] = cmax[lp][x];
            if(g[i] <= x && cmax[lp][x-g[i]] + c[i] > cmax[lc][x]){
                cmax[lc][x] = cmax[lp][x-g[i]]+c[i];
                }
            }
        lp = 1-lp; lc = 1-lc;
        }
}