#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N, G;
vector<int> c, g, cmax;
vector< vector<int> > uz;

int main (int argc, char const *argv[])
{
	ifstream in ("rucsac.in");
	in >> N >> G;
	c.resize(N + 1);
	g.resize(N + 1);
	cmax.resize(G + 1);
	uz.resize(G + 1, vector<int>(N + 1));
	for (int i = 1; i <= N; i++)
	{
		in >> g[i] >> c[i];
	}
	in.close();
	/*
	for (int i = 1; i <= N; i++)
	{
		cout << g[i] << ' ' << c[i] << '\n';
	}
	cout << '\n';
	*/
	for	(int S = 1; S <= G; S++)
		cmax[S] = -1;
		
	for (int S = 1; S <= G; S++)
	{
		for (int i = 1; i <= N; i++)
			if (g[i] <= S && cmax[S - g[i]] != -1 && !uz[S - g[i]][i])
				if (cmax[S] < c[i] + cmax[S - g[i]])
				{
					cmax[S] = c[i] + cmax[S - g[i]];
					for (int k = 1; k <= N; k++)
						uz[S][k] = uz[S - g[i]][k];
					uz[S][i] = 1;
				}
	}
			
	
	ofstream out ("rucsac.out");
	out << cmax[G];
	out.close();
	
	return 0;
}