#include <iostream>
#include <vector>

using namespace std;

#define NMAX 5005

// Solves the simple knapsack problem for one bag and a number of objects with weight and profit
class rucsac
{
	public:
	int pmax(vector <int> weight, vector <int> profit, int W)
	{
		int N = weight.size();
		vector <int> best[2];
		best[0].resize(W+1, 0);
		best[1].resize(W+1, 0);

		int prev, cur = 0;
		for (int i = 1; i <= N; ++i)
		{
			cur = !cur;
			prev = !cur;

			for (int w = 0; w <= W; ++w)
			{
				best[cur][w] = best[prev][w];
				if (weight[i-1] <= w) best[cur][w] = 
					max(best[cur][w], best[prev][w - weight[i-1]] + profit[i-1]);
			}

		}

		int ans = best[cur][0];
		for (int w = 1; w <= W; ++w) ans = max(ans, best[cur][w]);

		return ans;
	}

	int pmax_gen(vector <int> weight, vector <int> profit, int W)
	{
		return 0;
	}
};

int main()
{
	freopen ("rucsac.in", "r", stdin);
	freopen ("rucsac.out", "w", stdout);

	int N, G;
	vector <int> w, p;

	cin >> N >> G;
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		w.push_back(a);
		p.push_back(b);
	}

	int sol = (new rucsac())->pmax(w, p, G);
	cout << sol;

	return 0;
}