#include <bits/stdc++.h>
#define MAXN 5000
#define MAXG 10000
#define X(p) p.first
#define Y(p) p.second

using namespace std;

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

int n, g, dp[MAXG + 10], lastDp[MAXG + 10];
pair<int, int> objects[MAXN];

int main() {
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
        fin >> X(objects[i]) >> Y(objects[i]);
    for (int i = 1; i <= n; i++) {
        for (int cw = 0; cw <= g; cw++) {
            dp[cw] = lastDp[cw];
            if (X(objects[i]) <= cw)
                dp[cw] = max(dp[cw], lastDp[cw - X(objects[i])] + Y(objects[i]));
        }
        for (int cw = 0; cw <= g; cw++)
            lastDp[cw] = dp[cw];
    }

    fout << dp[g];
    return 0;
}