#include<stdio.h>
#include<utility>
#include<algorithm>

using namespace std;

FILE *in, *out;

//definitions
#define load first
#define price second

//constants
const int sz = (int) 5e3+1;
const int Gmax = (int) 1e3+1;

//variables
int nObj;
int weight;
pair<int, int> object[sz];
int Cmax[Gmax];

bool use[sz][Gmax];
int answer;

//functions

int main(void)
{
	in = fopen("rucsac.in", "rt");
	out = fopen("rucsac.out", "wt");
	
	fscanf(in, "%d%d", &nObj, &weight);
	
	for(int i=1; i<=nObj; ++i)
		fscanf(in, "%d%d", &object[i].load, &object[i].price);
	
	for(int S=1; S<=weight; ++S)
		Cmax[S] =-1;
	
	for(int S=1; S<=weight; ++S)
	{
		for(int i=1; i<=nObj; ++i)
		{
			if(object[i].load <= S && Cmax[S-object[i].load]!=-1 && !use[i][S-object[i].load])
				if(Cmax[S] < object[i].price + Cmax[S-object[i].load])
				{
					Cmax[S] = object[i].price + Cmax[S-object[i].load];
					for(int k=1; k<=nObj; ++k)
						use[k][S] = use[k][S-object[i].load];
					use[i][S] = true;
					
					answer = max(answer, Cmax[S]);
				}
		}
	}		
	
	fprintf(out, "%d", answer);
	
	fclose(in);
	fclose(out);
	return 0;
}