//// Arhiva Educationala 050 - Problema rucsacului

#include <stdio.h>
#include <vector>

using namespace std;

const char inFileName[] = "rucsac.in";
const char outFileName[] = "rucsac.out";
const int bad_profit = -1;

int main(int argc, char* argv[])
{
	FILE *inFile = NULL;
	FILE *outFile = NULL;
	vector<pair<short, short>> objects;
	short objectNumber, maxWeight;
	short x, y, weight, profit;
	int *recursionLine, maxProfit;
	
	
	inFile = fopen(inFileName, "rt");
	if (inFile == NULL)
		return -1;
	outFile = fopen(outFileName, "wt");
	if (outFile == NULL)
		return -2;

	fscanf(inFile, "%hd %hd", &objectNumber, &maxWeight);

	// allocate memory for the vector to reduce realloc overhead
	objects.reserve(objectNumber);
	// allocate memory for the recursion line
	recursionLine = new int[maxWeight + 1];

	for (short i = 0; i < objectNumber; i++)
	{
		fscanf(inFile, "%hd %hd", &x, &y);
		objects.push_back(make_pair(x, y));
		recursionLine[i] = bad_profit;

	}

	recursionLine[0] = 0;

	for (short i = 0; i < objectNumber; i++)
	{
		weight = objects[i].first;
		profit = objects[i].second;
		
		if (weight > maxWeight)
		{
			continue;
		}

		for (short w = maxWeight - weight; w >= 0; w--)
		{
			if (recursionLine[w] >= 0 && recursionLine[w] + profit > recursionLine[w + weight])
			{
				recursionLine[w + weight] = recursionLine[w] + profit;
			}
		}
	}

	// get the max profit
	maxProfit = -1;
	for (int i = 0; i <= maxWeight; i++){
		if (recursionLine[i] > maxProfit)
			maxProfit = recursionLine[i];
	}

	// output the result
	fprintf(outFile, "%d\n", maxProfit);

	delete[] recursionLine;
	fclose(inFile);
	fclose(outFile);
	return 0;
}