#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int v[10001],n,G,i,j,w[10001],p[10001],pmax;
void citire()
{
    fin>>n>>G;
    for(i=1;i<=n;i++)
            fin>>w[i]>>p[i];

}
int main()

{ citire();v[0]=1;
for(i=1;i<=n;i++)
 for(j=G-w[i];j>=0;j--)
 if(v[j]!=0)
 { v[j+w[i]]=v[j]+p[i];
   if(v[j+w[i]]>pmax)
     pmax=v[j+w[i]];
 }
    fout<<pmax-1;
    return 0;
}