#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");

int N, G, Pmax;
int W[10001], P[10001], D[5001][10001];

int main()
{
	int i, cw;
	fscanf(f,"%d%d", &N, &G);
	for(i=1; i<=N; i++)
		fscanf(f,"%d%d", &W[i], &P[i]);
	
	for(i=1; i<=N; i++)
		for(cw=0; cw<=G; cw++)
		{
			D[i][cw]=D[i-1][cw];		// nu pun obiectul i
			
			if(W[i]<=cw)
				D[i][cw]=max(D[i][cw], D[i-1][cw-W[i]] + P[i]);
			
		}
		
	Pmax=D[N][G];
	
	fprintf(g,"%d\n", Pmax);
	
	fclose(f);
	fclose(g);
	
	return 0;
}