#include<fstream>

#define MAXN 5001

using namespace std;

typedef int var;

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

var *DIN [MAXN];
var G[MAXN];
var P[MAXN];
var n, g;

//RECURENTA ESTE DIN[i][j] = MAX(DIN[i-G[i]][j-1] + P[i], DIN[i][j-1]

int main() {
    fin>>n>>g;
    for(var i=1; i<=n; i++) {
        fin>>G[i]>>P[i];
    }
    DIN[1] = new var[g+1];
    DIN[1][0] = 0;
    for(var i=1; i<=g; i++) {
        if(i < G[1]) DIN[1][i] = 0;
        else DIN[1][i] = P[1];
        //fout<<DIN[1][i]<<" ";
    }
    //fout<<endl;
    for(var i=2; i<=n; i++) {
        delete[]DIN[i-2];
        DIN[i] = new var[g+1];
        DIN[i][0] = 0;
        for(var j=1; j<=g; j++) {
            if(j < G[i]) DIN[i][j] = DIN[i-1][j];
            else DIN[i][j] = max(DIN[i-1][j-G[i]] + P[i], DIN[i-1][j]);
            //fout<<DIN[i][j]<<" ";
        }
        //fout<<endl;

    }
    fout<<DIN[n][g];
    return 0;
}