/*
    Keep It Simple!
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<stdio.h>
#define MaxN 5005
#define MaxG 10005
#define MaxV(a,b) ((a)>(b)?(a):(b))

int N,G;
int Weight[MaxN], Value[MaxN];
int Dp[MaxG];

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

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

	for (int i = 1; i <= N; i++)
		scanf("%d%d", &Weight[i], &Value[i]);

	for (int i = 1; i <= N; i++)
	for (int j = G; j >= Weight[i]; j--)
		Dp[j] = MaxV(Dp[j], Dp[j - Weight[i]] + Value[i]);
	printf("%d", Dp[G]);
	return 0;
}