#include <fstream>
using namespace std;
#define NMax 5005
#define GMax 10005
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int D[GMax], P[NMax], W[NMax];
int n,g,sol;
int main()
{
   fin>>n>>g;
   int i,j;
   for(i=1;i<=n;i++)
    fin>>W[i]>>P[i];
    D[0]=0;
    sol=0;

    for(i=1;i<=n;i++)
        for(j=g-W[i];j>=0;--j)
        {
            D[j+W[i]]=max(D[j+W[i]],P[i]+D[j]);
            sol=max(sol,D[j+W[i]]);
        }
   fout<<sol;
    return 0;
}