#include <cstdio>
#include <iostream>

using namespace std;

#define maxN 10005

int N , G , w[maxN] , p[maxN] , a[3][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)
		{
			a[i & 1][j] = a[(i - 1) & 1][j];
			
			if (w[i] <= j)
				a[i & 1][j] = max (a[i & 1][j] , a[(i - 1) & 1][j - w[i]] + p[i]);
		}

	printf ("%d" , a[N & 1][G]);
	
	return 0;
}