#include <cstdio>

using namespace std;

int maxprofits[10005];

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

	int n, g, i, j, maxweight=0, newmax;

	scanf("%d%d", &n, &g);

	int weights[n+1], profit[n+1];

	maxprofits[0]=1;

	for(i=1; i<=n; ++i)
		scanf("%d%d", &weights[i], &profit[i]);

	for(i=1; i<=n; ++i)
	{
		newmax = maxweight;
		for(j=maxweight; j>=0; --j)
			if(maxprofits[j]!=0 && j+weights[i]<=g && maxprofits[j] + profit[i]>maxprofits[j+weights[i]])
			{
				if(j+weights[i] > newmax)
					newmax = j+weights[i];
				maxprofits[j+weights[i]] = maxprofits[j] + profit[i];
			}
		maxweight = newmax;
	}

	newmax = 0;

	for(i=1; i<=maxweight; ++i)
		if(maxprofits[i]>newmax)
			newmax = maxprofits[i];

	printf("%d\n", newmax-1);

	return 0;
}