#include <stdio.h>
#define NMAX 5005
#define GMAX 10010

int A[2][GMAX], W[NMAX], P[NMAX];
int N, G;

inline int max(int a, int b)
{
    return (a>b)?a:b;
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int i, cw;
    scanf("%d %d", &N, &G);
    for (i=1; i<=N; ++i)
	scanf("%d %d", &W[i], &P[i]);
    
    int l = 0;
    for (i=1; i<=N; ++i, l = 1^l)
	for (cw=0; cw<=G; ++cw) {
	    A[1^l][cw] = A[l][cw];
	    if (W[i] <= cw)
		A[1^l][cw] = max(A[l][cw], A[l][cw-W[i]] + P[i]);
	}
    printf("%d\n", A[l][G]);
    return 0;
}