#include <iostream>
#include<fstream>
using namespace std;
int prof[20001];
int minim(int a,int b)
{
    if(a<b) return a;
    else return b;
}
int main()
{int n,G,gr[5001],val[5001],i,j,sum=0;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>G;
for(i=1;i<=n;i++)
    f>>gr[i]>>val[i];
for(i=1;i<=n;i++)
     {for(j=minim(sum,G);j>=1;j--)
        if(prof[j]+val[i]>prof[j+gr[i]]) prof[j+gr[i]]=prof[j]+val[i];
     if(prof[gr[i]]<val[i]) prof[gr[i]]=val[i];
     sum=sum+gr[i];
     }
for(i=G;i>=1;i--)
if(prof[i]!=0) {g<<prof[i];break;}
if(i==0) g<<0;
f.close();
g.close();
    return 0;
}