#include <fstream>

using namespace std;

int c[5001],g[5001],fin[10001];

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

int main()
{
    int n,G,sol=0,i,j;
    in>>n>>G;
    for (i=1;i<=n;i++)
        in>>g[i]>>c[i];
    for (i=1;i<=n;i++)
      for (j=G-g[i];j>=0;j--)
         if (fin[j+g[i]]<fin[j]+c[i])
         {
           fin[j+g[i]]=fin[j]+c[i];
           sol=max(sol,fin[j+g[i]]);
         }
    out<<sol;
    return 0;
}