#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

#define maxG 10005
#define maxN 5005

int dp[4][maxG], W[maxN], P[maxN];

int main()
{
	freopen ("rucsac.in", "r", stdin);
	freopen ("rucsac.out", "w", stdout);
	
	int N, G;
	
	scanf ("%d %d", &N, &G);
	
	for (int i = 1; i <= N; ++ i) scanf ("%d %d", &W[i], &P[i]);
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= G; ++ j)
			if (j - W[i] >= 0) dp[i % 2][j] = max (dp[! (i % 2)][j], dp[! (i % 2)][j - W[i]] + P[i]);
			else dp[i % 2][j] = dp[! (i % 2)][j];
	
	printf ("%d", dp[N % 2][G]);
	
	return 0;
}