#include <fstream>
using namespace std;

#define NMax 5005

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

int N,G;
int W[NMax],P[NMax];
int D[NMax];
int sol;

int main()
{
    int i,j;

    f>>N>>G;
    for(i=1;i<=N;++i)
    {
        f>>W[i]>>P[i];
    }

    D[0] = 0;
    sol = 0;

    for(i=1;i<=N;++i) for(j=G-W[i];j>=0;--j) if(D[j+W[i]] < D[j] + P[i])
    {
        D[j+W[i]] = D[j] + P[i];
        if(sol < D[j+W[i]]) sol = D[j+W[i]];
    }

    g<<sol<<"\n";

    f.close();
    g.close();
    return 0;
}