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

using namespace std;

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

int w[NMAX + 1], p[NMAX + 1], dp[2][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; j++) {
            if(j < w[i])
                dp[i%2][j] = dp[(i - 1)%2][j];
            else
                dp[i%2][j] = max(dp[(i - 1)%2][j], dp[(i - 1)%2][j - w[i]] + p[i]);
        }
    }

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

    printf ("%d", pmax);

    return 0;
}