#include<stdio.h>
#define GMAX 10100
#define INF 10100

int D[GMAX];

int main()
{
	int N, G, i, gnow = 0, w, p, sol = INF * (-1);

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

	scanf("%d%d", &N, &G);
	for(i = 1; i <= N; i ++)
		D[i] = INF * (-1);

	while(N --)
	{
		scanf("%d%d", &w, &p);
		for(i = gnow; i >= 0; i --)
			if(i + w <= G && D[i + w] < D[i] + p)
				D[i + w] = D[i] + p;
		gnow = gnow + w;
		if(gnow > G)
			gnow = G;
	}

	for(i = 1; i <= G; i ++)
		if(D[i] > sol)
			sol = D[i];
	printf("%d", sol);

	return 0;
}