#include <bits/stdc++.h>
std::ifstream cin("rucsac.in");
std::ofstream cout("rucsac.out");
long long n,max,v[5010],g[5010],sum[5010],ans;
void bkt(long long poz,long long sumg,long long sumv)
{
    ans=std::max(ans,sumv);
    if(poz>n||sumv+sum[poz]<=ans)
        return;
    if(sumg+g[poz]<=max)
        bkt(poz+1,sumg+g[poz],sumv+v[poz]);
    bkt(poz+1,sumg,sumv);
}
int main()
{
    cin>>n>>max;
    for(int i=1;i<=n;++i)
        cin>>g[i]>>v[i];
    for(int i=n;i>=1;--i)
        sum[i]=sum[i+1]+v[i];
    bkt(1,0,0);
    cout<<ans;
    return 0;
}