#include <fstream>
using namespace std;

int v[10001];

int main(){
	
	v[0] = 1;

	ifstream in("rucsac.in");
	ofstream out("rucsac.out");

	int n, g, cv, cg, j;
	in >> n >> g;

	for (int i = 0; i < n; i++){
		in >> cg >> cv;
		
		for (j = (g - cg > 0) ? g - cg : 0; j >= 0; j--)
			if (v[j] && v[j + cg] < v[j] + cv)
				v[j + cg] = v[j] + cv;
	}

	int maxim = 0;

	for (int i = 0; i <= g; i++)
		if (v[i] > maxim)
			maxim = v[i];
	out << maxim - 1;
}