#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, nr, r;
bool bn[3][10004];

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