#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("rucsac.in");
ofstream g("date.out");

int main()
{
    int n,g,v[5001],p[5001],i,maxi=26,va,pa,k,j,s;
    f>>n>>g;
    for(i=1;i<=n;i++)
        f>>v[i]>>p[i];

    k=pow(2,n)-1;
    for(i=50;i<=k;i++)
        {
            j=1;s=i;va=0;pa=0;
            while(s)
            {
                if(s%2)
                {
                    va+=v[j];
                    pa+=p[j];


                }
                s=s/2;j++;
            }
            if(va<=g and maxi<pa)
                {maxi=pa;
                g<<i<<' ';}
        }
        cout<<maxi;
    return 0;
}