#include<stdio.h>

FILE *file;
int N, G, profit[10001], weight[5001], gain[5001];

int main()
{
	int i, j;
	
	file = fopen("rucsac.in", "r");
	fscanf(file, "%d %d", &N, &G);
	for(i = 1; i <= N; ++i)
		fscanf(file, "%d %d", &weight[i], &gain[i]);
	fclose(file);
	
	for(i = 1; i <= N; ++i)
		for(j = G; j >= 0; --j)
			if(j - weight[i] >= 0 && (profit[j - weight[i]] + gain[i] > profit[j]))
				profit[j] = profit[j - weight[i]] + gain[i];
	
	file = fopen("rucsac.out", "w");
	fprintf(file, "%d\n", profit[G]);
	fclose(file);
	
	return 0;
}