#include <fstream>
#define NMAX 5002
#define GMAX 5002
using namespace std;
void citire();
void pd();
void afisare();
int n, G, g[NMAX], c[NMAX], lp, lc;
int cmax[2][GMAX];
int main() {
    citire();
    pd();
    afisare();
    return 0;
}
void citire() {
    ifstream fin("rucsac.in");
    int i;
    fin>>n>>G;
    for (i = 1; i <= n; i++) fin>>g[i]>>c[i];
}
void afisare() {
    ofstream fout("rucsac.out");
    fout<<cmax[lp][G]<<'\n';
    fout.close();
}
void pd() {
    int lc = 1, lp=0, 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;
        }
}