#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[2][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 <= 1; 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 % 2][j] = dp[(i - 1) % 2][j];
            if (j - v[i].f >= 0) {
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - v[i].f] + v[i].s);
            }
        }
    }
    int r = INT_MIN;
    for (int i = 1; i <= g; i++) {
        r = max(r, dp[n % 2][i]);
    }
    out << r;
    fin.close();
    fout.close();
    return 0;
}