#include <cstdio>
using namespace std;

#define Nmax 5002
#define Gmax 10002

FILE *fi = fopen("rucsac.in", "r");
FILE *fo = fopen("rucsac.out", "w");

int n;
int g;
int p[Nmax];
int w[Nmax];
int sol[Gmax];
int s = 0;


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

int main()
{
	fscanf(fi, "%d%d", &n, &g);
	for (int i = 1; i<=n; i++)
		fscanf(fi, "%d%d", &w[i], &p[i]);
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = g; j >= w[i]; --j)
		{
			sol[j] = maxim(sol[j], sol[j-w[i]] + p[i]);
			if (sol[j] > s) s = sol[j];
		}
	}

	fprintf(fo, "%d\n", s);
	
	return 0;
}