#include <stdio.h>
#include <algorithm>
#define IN "rucsac.in"
#define OUT "rucsac.out"

using namespace std;

const int MaxN = 5005;
const int MaxG = 10005;

int Mat[2][MaxG];
int N, G, L;
int W[MaxN], P[MaxN];

int main()
{
    freopen (IN , "r" , stdin);
    freopen (OUT , "w" , stdout);

    scanf ("%d %d", &N, &G);

    for (int i = 0 ;  i < N ; i++)
        scanf ("%d %d", (W + i), (P + i));

    for (int i = 0 ; i < N ; i ++, L = 1 - L)
        for (int j = 0 ; j <= G ; j ++)
        {
            Mat[L][j] = Mat[1 - L][j];

            if (W[i] <= j)
                Mat[L][j] = max( Mat[1 - L][j], Mat[1 - L][j - W[i]] + P[i]);
        }

    printf("%d\n", Mat[1 - L][G]);

    return 0;
}