#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G,greutate[5001],pret[5001],sol[5001][10001];
int main()
{
    f>>N>>G;
    for(int i=1;i<=N;++i)
        f>>greutate[i]>>pret[i];
    for(int i=1;i<=N;++i)
        for(int gc=0;gc<=G;++gc)
        {
            sol[i][gc]=sol[i-1][gc];
            if(gc>=greutate[i])
                sol[i][gc]=max(sol[i][gc],(sol[i-1][gc-greutate[i]]+pret[i]));
        }
    g<<sol[N][G];
    g.close();
    return 0;
}