#include <fstream>

using namespace std;
int v[10001];
int main()
{
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,g,a,b,m=0;
cin>>n>>g;
v[0]=1;
for(int i=0;i<n;i++)
{
    cin>>b>>a;
    for(int j=g;j>=0;j--)
    {
        if(v[j]!=0 && j+b<=g)
        v[j+b]=max(v[j+b],v[j]+a);
    }
}
for(int i=0;i<=g;i++)
m=max(m,v[i]);
cout<<m-1;
    return 0;
}