#include <stdio.h>
#include <iostream>
#define NMAX 5005
#define GMAX 10005

using namespace std;

int weight[NMAX], profit[NMAX];
int DP[GMAX];

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

    int n, g, i, j; scanf("%d%d", &n, &g);
    for (i = 1; i <= n; ++i) scanf("%d%d", &weight[i], &profit[i]);

    for (i = 1; i <= n; ++i)
        for (j = g; j >= 1; --j)
            if (weight[i] <= j) DP[j] = max(DP[j], profit[i] + DP[j - weight[i]]);

    printf ("%d\n", DP[g]);
    return 0;
}