#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct items { int weight, value, index; }*item;
int bag_capacity, items_nr, **M;

void read(char *file)
{
	ifstream in(file);
	in >> items_nr >> bag_capacity;
	item = new items[items_nr];
	M = new int*[items_nr];

	for (int i = 0; i < items_nr; i++)
	{
		M[i] = new int[bag_capacity + 1];
		for (int j = 0; j <= bag_capacity; j++)
			M[i][j] = -1;
	}

	for (int i = 0; i < items_nr; i++)
	{
		in >> item[i].weight >> item[i].value;
		item[i].index = i + 1;
	}
	in.close();
}

void merge(int left, int middle, int right)
{
	int i = left, j = middle + 1, k = 0;
	items *temp = new items[right - left + 1];

	while (i <= middle && j <= right)
	{
		if ((float)item[i].value/item[i].weight < (float)item[j].value/item[j].weight) { temp[k] = item[i]; i++; k++; }
		else { temp[k] = item[j]; j++; k++; }
	}
	while (i <= middle) { temp[k] = item[i]; i++; k++; }
	while (j <= right) { temp[k] = item[j]; j++; k++; }

	for (int c = 0; c < k; c++)
	{
		item[left + c] = temp[c];
	}
}

int KS(int i, int j)
{
	if (i == 0)
	{
		if (item[i].weight <= j) M[i][j] = item[i].value;
		else M[i][j] = 0;
	}
	else if (j - item[i].weight >= 0)
	{
		if (M[i - 1][j - item[i].weight] == -1 && M[i - 1][j] == -1)
			M[i][j] = max(item[i].value + KS(i-1, j-item[i].weight), KS(i-1,j));
		else if(M[i-1][j-item[i].weight] == -1)
			M[i][j] = max(item[i].value + KS(i - 1, j - item[i].weight), M[i - 1][j]);
		else if(M[i - 1][j] == -1)
			M[i][j] = max(item[i].value + M[i - 1][j - item[i].weight], KS(i - 1, j));
		else
			M[i][j] = max(item[i].value + M[i - 1][j - item[i].weight], M[i - 1][j]);
	}
	else
	{
		if (M[i - 1][j] == -1)
			M[i][j] = KS(i - 1, j);
		else
			M[i][j] = M[i - 1][j];
	}

	return M[i][j];
}

void merge_sort(int left, int right)
{
	if (left < right)
	{
		int middle = (left + right) / 2;
		merge_sort(left, middle);
		merge_sort(middle + 1, right);

		merge(left, middle, right);
	}
}
void generate_objects(int i, int j)
{
	if (i > 0)
	{
		while (M[i][j] - item[i].value != M[i - 1][j - item[i].weight]) i--;
		j -= item[i].weight;
		cout << item[i].weight << " " << item[i].value << endl;
		generate_objects(--i, j);
	}
	else
	{
		if(j - item[i].weight == 0) cout << item[i].weight << " " << item[i].value << endl;
		else return;
	}
}

int main()
{
	read("rucsac.in");
	merge_sort(0, items_nr-1);
	ofstream out("rucsac.out");
	out<<KS(items_nr - 1, bag_capacity);
	out.close();
	//generate_objects(items_nr - 1, bag_capacity);
	return 0;
}