#include<stdio.h>

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

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