#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>
#include "TAP_Lab_7.h"

using std::cout;

using std::ifstream;
using std::ofstream;

using std::vector;

using std::max;

struct Item {
	int _w, _c;

	Item(int w = 0, int c = 0) : _w(w), _c(c) {}
};

int dynamic(vector<Item> items, int g) {
	vector< vector<int> > m(items.size() + 1);
	for (int i = 0; i <= items.size(); i++) {
		for (int j = 0; j <= g; j++) {
			m[i].push_back(INT_MIN);
		}
	}

	m[0][0] = 0;

	for (int i = 1; i <= items.size(); i++) {
		for (int j = 0; j <= g; j++) {
			if (j - items[i - 1]._w >= 0)
				m[i][j] = max(items[i - 1]._c + m[i - 1][j - items[i - 1]._w], m[i - 1][j]);
			else
				m[i][j] = m[i - 1][j];
		}
	}

	int wmax = m[items.size()][0];

	for (int i = 1; i <= g; i++) {
		if (m[items.size()][i] > wmax) {
			wmax = m[items.size()][i];
		}
	}

	return wmax;
}

int main() {
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");

	int n, g;
	in >> n >> g;
	vector<Item> items;

	while (n--) {
		int w, c;
		in >> w >> c;
		items.push_back(Item(w, c));
	}

	out << dynamic(items, g);
}