//https://www.infoarena.ro/problema/rucsac
#include <fstream>
#include <vector>

std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");

using namespace std;

vector<int> dp, v, g;

int maxim(int a, int b)
{
	return a > b ? a : b;
}
int main()
{
	int n, G, sol = 0;
	fin >> n >> G;
	v.resize(n);
	g.resize(n);
	dp.resize(G + 1, 0);
	dp[0] = 1;
	for (int i = 0; i < n; ++i)
		fin >> g[i] >> v[i];

	for (int i = 0; i < n; ++i)
		for (int j = G; j >= 0; --j)
			if (dp[j] != 0 && g[i] + j <= G)
			{
				dp[j + g[i]] = maxim(dp[j + g[i]], dp[j] + v[i]);
				sol = maxim(sol, dp[j + g[i]]);
			}
	fout << -1 + sol;
}