#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (a) < (b) ? (b) : (a)

int main()
{
	FILE * f = fopen("rucsac.in","r");

	int n,g;
	fscanf(f, "%i%i", &n,&g);
	int	v[5000][2];

	int i;
	for (i = 0; i < n; i++)
	{
		fscanf(f,"%i%i",v[i],v[i]+1);
	}

	fclose(f);

	int j,m[2][10003] =  {0};

	int k = 0;
	for (i = 0; i < n; i++)
	{
		k = k ^ 1;
		for (j = 1; j <= g; j++)
		{
			m[k][j] = max(m[k-(k == 0? -1 : 1)][j],j - v[i][0] < 0?-1:(m[k - (k==0?-1:1)][j - v[i][0]] + v[i][1]));
		}	
	
	}

	f = fopen("rucsac.out","w");
	fprintf(f,"%i",m[k][g]);
	fclose(f);
	return 0;
}