#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N,G,W[5001],P[5001],Optim[10001],sol;

int main()
{
    int i,j;
    f>>N>>G;
    for (i=1;i<=N;i++)
        f>>W[i]>>P[i];
    for (i=1;i<=N;i++)
        for(j=G-W[i];j>=0;j--)
            if(Optim[j+W[i]]<Optim[j]+P[i])
                {
                    Optim[j+W[i]]=Optim[j]+P[i];
                    if(sol<Optim[j+W[i]])
                        sol=Optim[j+W[i]];
                }
    g<<sol;
    return 0;
}