#include <iostream>
#include <fstream>

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

int i, cw, n, g, a, b, x, y, rc[3][10004], mx;

int main () {
    
    fin >> n >> g;
    fin >> a >> b;
    rc[1][a] = b;
    x = 1;  y = 2;
    
    for (i = 2; i <= n; i++)
    {
        fin >> a >> b;
    
        for (cw = 0; cw <= g; cw++)
        {
            rc[y][cw] = rc[x][cw];
            
            if (a <= cw)
                rc[y][cw] = max(rc[y][cw], rc[x][cw-a]+b);
        }
        
        a = x;
        x = y;
        y = a;
    }
    
    fout << rc[x][g] << "\n";
}