//
//  main.cpp
//  rucsac
//
//  Created by Razvan Paul Birgaoanu on 13/12/16.
//  Copyright © 2016 Razvan Paul. All rights reserved.
//

#include <fstream>
#define NMAX 5002
#define GMAX 10002

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int n, G, lc = 1, lp = 0;
int g[GMAX], c[NMAX];
int cmax[2][GMAX];

void read();
void dp();
void print();

int main(int argc, const char * argv[]) {
    
    read();
    dp();
    print();

    return 0;
}

void read() {
    in >> n >> G;
    for (int i = 1; i <= n; ++i) {
        in >> g[i] >> c[i];
    }
}

void dp() {
    int lc = 1, lp = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int x = 1; x <= G; ++x) {
            cmax[lc][x] = cmax[lp][x];
            if (g[i] <= x && cmax[lp][x-g[i]] + c[i] > cmax[lc][x]) {
                cmax[lc][x] = cmax[lp][x-g[i]] + c[i];
            }
        }
        lp = 1 - lp;
        lc = 1 -lc;
    }
}

void print() {
    out << cmax[lp][G] << '\n';
    out.close();
}