#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[2][GMAX];

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

    int l = 0;
    for (int i = 1; i <= N; i++, l = 1 - l)
        for (int cw = 0; cw <= G; cw++) {
            DP[1-l][cw] = DP[l][cw];
            if (W[i] <= cw)
                DP[1-l][cw] = max(DP[1-l][cw], DP[l][cw - W[i]] +  P[i]);
        }
    g << DP[l][G];
}