#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <vector>

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")

using namespace std;

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

#define in fin
#define out fout
#define f first
#define s second

int dp[5005][10005];

signed main() {
    int n, g;
    in >> n >> g;
    vector<pair<int, int>> v(n + 1);
    for (int i = 1; i <= n; i++) {
        in >> v[i].f >> v[i].s;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= g; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= g; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - v[i].f >= 0) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].f] + v[i].s);
            }
        }
    }
    int r = INT_MIN;
    for (int i = 1; i <= g; i++) {
        r = max(r, dp[n][i]);
    }
    out << r;
    fin.close();
    fout.close();
    return 0;
}