#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 = 0; i < n; i++)
        fin >> X(objects[i]) >> Y(objects[i]);
    for (int i = 0; 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 j = 0; j <= g; j++)
            lastDp[j] = dp[j];
    }
    fout << dp[g];
    return 0;
}