#include <bits/stdc++.h>
using namespace std;

struct item {
    int w, p;
} v[5001];

int n, g;
int dp[10001];

int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    cin >> n >> g;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].w >> v[i].p;
    }
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = g - v[i].w; j >= 0; --j) {
            if (dp[j] != -1) {
                dp[j + v[i].w] = max(dp[j + v[i].w], dp[j] + v[i].p);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= g; ++i) {
        ans = max(ans, dp[i]);
    }
    cout << ans;
}