#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int d[10000][10000];
int w[5000], p[5000];
int n, i, G, cw, pmax;

int main ()
{
    f >> n >> G;
    for (i=1; i<=n; i++)
        f >> w[i] >> p[i];
    for (i=1; i<=n; i++)
        for (cw=0; cw<=G; cw++)
            d[i][cw] = max (d[i-1][cw], d[i-1][cw-w[i]]+p[i]);
    pmax = d[n][G];
    g << pmax;
    return 0;
}