#include "stdio.h"

#define MAX_N 5001
#define MAX_G 10001

FILE *f, *g;
int weight[MAX_N];
int profit[MAX_N];
int N, G;

int optim[MAX_G];
int solution;

int main()
{
	f = fopen("rucsac.in", "r");
	g = fopen("rucsac.out", "w");

	fscanf(f, "%d", &N);
	fscanf(f, "%d", &G);

	for(int i = 1; i <= N; i++)
	{
		fscanf(f, "%d", &weight[i]);
		fscanf(f, "%d", &profit[i]);
	}

	optim[0] = 0;
	solution = 0;

	for(int i = 1; i <= N; i++)
		for(int j = G - weight[i]; j >= 0; j--)
		{
			if(optim[j+weight[i]] < optim[j] + profit[i])
			{
				optim[j+weight[i]] = optim[j] + profit[i];
				if(optim[j+weight[i]] > solution)
					solution = optim[j+weight[i]];
			}
		}

	fprintf(g, "%d", solution);

	fclose(f);
	fclose(g);

	return 0;
}