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

using namespace std;

#define maxN 5005
#define maxG 10005

int dp[3][maxG];
int N , G , P[maxN] , W[maxN];

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" , &W[i] , &P[i]);
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1 ; j <= G ; ++j)
		{
			if (W[i] > j)
				continue;
			
			dp[i & 1][j] = max (dp[(i - 1) & 1][j] , dp[(i - 1) & 1][j - W[i]] + P[i]);
		}
	
	printf ("%d" , dp[N & 1][G]);
	
	return 0;
}