#include <iostream>
#include <stdio.h>

using namespace std;

const int NMAX = 5000;
const int GMAX = 10000;

int w[NMAX + 1], p[NMAX + 1], dp[NMAX + 1][GMAX + 1];

int main() {

    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);

    int n, g, i, j, pmax;

    scanf("%d%d", &n, &g);
    for (i = 1; i <= n; i++)
        scanf ("%d%d", &w[i], &p[i]);

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

    pmax = 0;
    for (j = 0; j <= g; j++)
        pmax = max(pmax, dp[n][j]);

    printf ("%d", pmax);

    return 0;
}