#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int w[10001],p[10001],pmaxn,G,i,gmx,s[20001],n,j,mx;
int main()
{
f>>n>>gmx;
for(i=1;i<=n;i++)
    f>>w[i]>>p[i];
for(i=1;i<=n;i++)
    for(j=mx;j>=0;j--)
    {
    if(s[j+w[i]]<s[j]+p[i]&&j+w[i]<=gmx&&(!j||s[j]))
         {
            s[j+w[i]]=s[j]+p[i];
            if(w[i]+j>mx) mx=w[i]+j;
         }
    }
  int sol=0;
    for(i=0;i<=gmx;i++)
        if(sol<s[i]) sol=s[i];
    g<<sol;

    return 0;
}