#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, g;
int w[5000], p[5000];
int b[10002];
int *now = new int[10002], *old = new int[10002];
void upd(int x, int y, int val){
    if((b[y] != x) && (b[y] != (x + 1))){
        now[y] = val;
    }else now[y] = max(now[y], val);
    b[y] = x + 1;
}
int main() {
    cin>>n>>g;
    for(int x = 0; x<n; x++)
        cin>>w[x]>>p[x];
    for(int x = 0; x<=10000; x++) {
        b[x] = false;
        now[x] = 0;
        old[x] = 0;
        b[x] = -1;
    }
    b[0] = 0;
    for(int x = 0; x<n; x++){
        for(int y = 0;y<=10000;y++){
            if((b[y] == x) || (b[y] == (x + 1))){
                upd(x, y, old[y]);
                if((y + w[x]) <= g)
                    upd(x, y + w[x], old[y] + p[x]);
            }
        }
        swap(now, old);
    }
    int maxv = -1;
    for(int x = 0;x<=g;x++)
        maxv = max(maxv, old[x]);
    cout<<maxv;
    return 0;
}