# include <algorithm>
# include <cstdio>
using namespace std;

const char *FIN = "rucsac.in", *FOU = "rucsac.out";
const int MAX_N = 5005, MAX_G = 10005;

int N, G, W[MAX_N], P[MAX_N], dp[2][MAX_G];

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &G);
    for (int i = 1; i <= N; ++i)
        scanf ("%d %d", W + i, P + i);
    for (int i = 1, K = 0; i <= N; ++i, K ^= 1)
        for (int g = 0; g <= G; ++g) {
            dp[K ^ 1][g] = dp[K][g];
            if (W[i] <= g) dp[K ^ 1][g] = max (dp[K ^ 1][g], dp[K][g - W[i]] + P[i]);
        }
    fprintf (fopen (FOU, "w"), "%d", dp[N & 1][G]);
}