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

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

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

int main(void) {
    int n, maxG, dp[10001];
    f >> n >> maxG;
    for (int i = 0; i < n; i++) {
        f >> item[i].w >> item[i].p;
    }

    dp[0] = 0;

    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        for (int j = maxG - item[i].w; j >= 0; j--) {
            dp[j + item[i].w] = max(dp[j + item[i].w], dp[j] + item[i].p);
            maxVal = max(maxVal, dp[j + item[i].w]);
        }
    }

    g << maxVal;
}