#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
	short n;
	short w;
	vector<short> weight;
	vector<short> p;
public:
	void readData() {
		ifstream f("rucsac.in");
		f >> n >> w;
		weight.resize(n + 1);
		p.resize(n + 1);
		for (int i = 1; i <= n; ++i) {
			f >> weight[i] >> p[i];
		}
	}

	/*
	n -  nr de  obiecte din colectie
	W - capacitatea maxima a rucsacului
	(w[i], p[i]) - caracteristicile obiectului i
	*/
	int rucsac() {
		/*
		dp - e o matrice de (n + 1) * (W + 1)
		pt folosim dp[0][*] pentru multimea vida
        dp[*][0] pentru situatia in care ghiozdanul are capacitate 0
		*/
		vector< vector<int> > dp(2);

		for (int i = 0; i <= 1; ++i) {
			dp[i].resize(w + 1);
		}

		// base case
		for (int cap = 0; cap <= w; ++cap) {
			dp[0][cap] = 0;
		}

		// general case
		for (int i = 1; i <= n; ++i) {
			for (int cap = 0; cap <= w; ++cap) {
				dp[i % 2][cap] = dp[(i - 1) % 2][cap];  // i don't use obj i => same sol as of iter i - 1

				// I use obj i, thus I have to reserve weight[i] units
				// => beforehand I must have in use at most cap - weight[i]
				if (cap - weight[i] >= 0) {
					int sol_aux = dp[(i - 1) % 2][cap - weight[i]] + p[i];
					dp[i % 2][cap] = max(dp[i % 2][cap], sol_aux);
				}

			}
		}
		return dp[n % 2][w];
	}

	void print() {
		ofstream g("rucsac.out");
		g << rucsac();
	}

};

int main() {
	Solution sol;
	sol.readData();
	sol.print();
}