#include <bits/stdc++.h>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n, g, d[10005];
int w[5005], p[5005];
int main()
{
    in >> n >> g;
    for (int i = 1; i <= n; i++) {
        in >> w[i] >> p[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = g; j - w[i] >= 0; j--) {
            d[j] = max(d[j], d[j - w[i]] + p[i]);
            ans = max(ans, d[j]);
        }
    }

    out << ans << '\n';
    return 0;
}