#include<fstream>
using namespace std;
int n, k, i, j, v[10003], maxim;
struct cub{
    int g;
    int val;
};
cub x[10003];
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main(){
    in>>n>>k;
    for(i=1; i<=n; i++){
        in>>x[i].g>>x[i].val;
        for(j=maxim; j>=1; j--){
            if(v[j]!=0 && j+ x[i].g<=k && v[j]+x[i].val>=v[j+x[i].g])
                v[j+x[i].g]=v[j]+x[i].val;
        }
        if(v[x[i].g]<x[i].val)
                v[x[i].g]=x[i].val;
            maxim+=x[i].g;
    }
    for(i=maxim; v[i]==0; i--){}
    out<<v[i];
    return 0;
}