#include <fstream>
int v[10005],i,e,c,n,m,nm;
using namespace std;
int main ()
{ifstream f("rucsac.in");
 ofstream g("rucsac.out");

nm=0;
f>>m>>n;
while(m)
{f>>e>>c;
for(i=nm;i>=0;i--)
if(v[i]||!i)
if(i+e<=n)
if(v[i+e])
v[i+e]=max(v[i]+c,v[i+e]);
else
v[i+e]=v[i]+c;
nm=min(n,e+nm);
m--;}
while(!v[n])
n--;
g<<v[n];

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