#include <bits/stdc++.h>
#define NMAX 5010
#define GMAX 10010

using namespace std;

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

int N, G, W[NMAX], P[NMAX], DP[GMAX], ans = INT_MIN;

int main() {
    f >> N >> G;
    for (int i=1; i<=N; i++)
        f >> W[i] >> P[i];

    for (int i=1; 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];
                if (DP[j + W[i]] > ans)
                    ans = DP[j + W[i]];
            }
    g << ans;
}