#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gm,gmax,p,pmax,i,j,a[10000],b[10000],x;
int main()
{f>>n>>gm;
for(i=1;i<=n;i++)f>>a[i]>>b[i];
for(i=1;i<=(1<<n);i++){
x=i;
gmax=0;
p=0;
for(j=1;j<=n;j++)
{if(x%2==1){
p=p+b[j];
gmax=gmax+a[j];
}x/=2;
}
if(p>pmax && gmax<=gm)pmax=p;
}
g<<pmax;


    return 0;
}