#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

#define MAXN 5010
#define MAXG 10010

int d[MAXN][MAXG];
int d1[MAXG], d2[MAXG];
int w[MAXN], p[MAXN];
int n, g;

int main() {
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
    for (int i = 1; i <= n; i++) {
        for (int cw = 1; cw <= g; cw++) {
            d2[cw] = d1[cw];
            if (w[i] <= cw) {
                d2[cw] = max(d1[cw], d1[cw - w[i]] + p[i]);
            }
        }
        for (int k = 1; k <= g; k++)
            d1[k] = d2[k];
    }
    int Pmax = d2[g];
    fout << Pmax;
    return 0;
}