#include <fstream>
#include <algorithm>
using namespace std;
const int MAXN = 5008;
const int MAXG = 10009;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G, Pmax;
int W[MAXN], P[MAXN];
int D[2][MAXG];
int main() {
    fin >> N >> G;
    for (int i = 1; i <= N; i++) {
        fin >> W[i] >> P[i];
    }
    int l = 0; 
    for (int i = 1; i <= N; i++, l = 1 - l) {
        for (int cw = 0; cw <= G; cw++) {
            D[1 - l][cw] = D[l][cw];
            if (W[i] <= cw) {
                D[1 - l][cw] = max(D[1 - l][cw], D[l][cw - W[i]] + P[i]);
            }
        }
    }
    Pmax = D[l][G];
    fout << Pmax;
    return 0;
}