#include <stdio.h>
#include <stdlib.h>
int N, G, g[5001], profit[5001], d[5001][5001];
int PD(int i,int greutate)
{
	if (i <= 0)
	{
		return 0;
	}
	if (greutate < 0)
	{
		return 0;
	}
	if (d[i][greutate] != 0)
	{
		return d[i][greutate];
	}
	int t1, t2;
	t1 = PD(i - 1, greutate);
	t2 = 0;
	if (g[i] <= greutate)
	{
		t2 = PD(i - 1, greutate - g[i]) + profit[i];
	}
	if (t1 < t2)
	{
		d[i][greutate] = t2;
		return t2;
	}
	d[i][greutate] = t1;
	return t1;
}
int main()
{
	FILE *f, *h;
	f = fopen("rucsac.in", "r");
	h = fopen("rucsac.out", "w");
	fscanf(f, "%d %d", &N, &G);
	for (int i = 1; i <= N; i++)
	{
		fscanf(f, "%d %d", &g[i], &profit[i]);
	}
	fprintf(h, "%d\n", PD(N, G));
	system("pause");
	
}