#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
using VI = vector<int>;
const string problem("rucsac");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
int n, g, res;
int main() {
    DAU
    fin >> n >> g;
    VI w(n + 1), p(n + 1);
    for (int i = 1; i <= n; ++i)
        fin >> w[i] >> p[i];
    VI dp(g + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = g - w[i]; j >= 0; --j)
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
    for (int j = 0; j <= g; ++j)
        res = max(res, dp[j]);
    fout << res;
    PLEC
}