#include <iostream>
#include <fstream>

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

long long i, cw, n, g, a, b, rc[3][10004];

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