#include <cstdio>

const int MAX_G(10001);

int max_profit [MAX_G];

int main (void)
{
	std::freopen("rucsac.in","r",stdin);
	std::freopen("rucsac.out","w",stdout);
	int n, g;
	std::scanf("%d%d",&n,&g);
	int weight, *weight_ptr(&weight), profit, *profit_ptr(&profit), i, new_weight, new_profit, best_profit(0);
	do
	{
		std::scanf("%d%d",weight_ptr,profit_ptr);
		for (i = g - weight, new_weight = i + weight ; i >= 0 ; --new_weight, --i)
		{
		 	new_profit = max_profit[i] + profit;
			if (max_profit[new_weight] < new_profit)
			{
				max_profit[new_weight] = new_profit;
				if (best_profit < new_profit)
					best_profit = new_profit;
			}
		}
		--n;
	}
	while (n);
	std::fclose(stdin);
	std::printf("%d\n",best_profit);
	std::fclose(stdout);
	return 0;
}