#include<fstream>
using namespace std;
int n, k, i, j, v[10003], maxim, sol;
struct cub{
    int g;
    int val;
};
cub x[5003];
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;
            if(x[i].g+maxim<=k)
                maxim+=x[i].g;
            else
                maxim=k;
    }
    for(i=maxim; i>=1; i--){
        if(v[i]>sol)
            sol=v[i];
    }
    out<<sol;
    return 0;
}