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

using namespace std;

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

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

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

    for(int i = 1; i <= n; i++){
        for(int 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;
    }

    fout << cmax[lp][G];

    return 0;
}