#include <bits/stdc++.h>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int maxn = 5e3 + 5;

struct obiect {
    int w, p;

} v[maxn];

int dp[maxn];

int main() {

    int n, g;

    int sol = 0;

    in >> n >> g;

    for (int i(1); i <= n; i++) {
        in >> v[i].w >> v[i].p;
    }

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

    out << sol;

    return 0;
}