#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G,w[5001],p[5001],sol[5001][10001];
int main()
{
    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 wc=0;wc<=G;++wc)
        {
            sol[l][wc]=sol[1-l][wc];
            if(wc>=w[i])
                sol[l][wc]=max(sol[l][wc],sol[1-l][wc-w[i]]+p[i]);
        }
    g<<max(sol[1-l][G],sol[l][G]);
    g.close();
}