// Ilie Dumitru
#include<bits/stdc++.h>
const int NMAX=5005, WMAX = 10005;

int N, W;
int max[WMAX];

int main()
{
	std::ifstream f("rucsac.in");
	std::ofstream g("rucsac.out");
	int i, j, w, p;

	f >> N >> W;
	max[0] = 1;
	for(i = 0;i < N;++i)
	{
		f >> w >> p;
		for(j = W;j >= w;--j)
			if(max[j - w] && max[j - w] + p > max[j])
				max[j] = p + max[j - w];
		max[w] = std::max(p + 1, max[w]);
	}

	for(i = W;i > -1 && !max[i];--i);

	g << max[i] - 1;

	return 0;
}