#include <bits/stdc++.h>

using namespace std;

const int len = 10005;
int n, g, w[len], p[len], dp[len], res;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    cin >> n >> g;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> p[i];

    for (int i = 0; i < n; i++)
        for (int j = g - w[i]; j >= 0; j--)
            if (dp[j + w[i]] < dp[j] + p[i]) {
                dp[j + w[i]] = dp[j] + p[i];
                res = max(res, dp[j + w[i]]);
            }

    cout << res;
}