#include<fstream>
#define maxn 5001
#define maxp 10001
using namespace std;
int n,p,sol;
int g[maxn], v[maxn];
int best[maxp];
int main() {
    ifstream in("rucsac.in"); ofstream out("rucsac.out");
    in>>n>>p;
    for (int i=1; i<=n; ++i)
        in>>g[i]>>v[i];
    for( int i=1; i<=n; ++i)
        for( int j=p-g[i]; j>=0; --j) {
            if( best[j+g[i]]<best[j]+v[i]){
                best[j+g[i]]=best[j]+v[i];
                if(best[j+g[i]]>sol)
                    sol=best[j+g[i]];
            }
    }
    out<<sol<<'\n';
    return 0;
}