#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,D[2][10005],sol;
int w[5000],p[5000];

int main ()
{
    int cw;
    f>>n>>G;
    for(int i=1;i<=n;i++)
        f>>w[i]>>p[i];
   int l=0;
    for(int i = 1; i <= n; ++i, l = 1 - l)
        for(int cw = 0; cw <= G; ++cw)
        {
            D[1-l][cw] = D[l][cw];

            if(w[i] <= cw)
                D[1-l][cw] = max(D[1-l][cw], D[l][cw - w[i]] + p[i]);
        }

    sol = D[l][G];
    g<<sol;
    return 0;
}