/*
 * rucsac.cpp
 *
 *  Created on: Mar 2, 2012
 *      Author: Tibi
 */
#define DEBUG 0

#if DEBUG==1
#include <stdio.h>
#warning Debug is ON
#endif

#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;



#define maxg 10008
#define maxn 5008

int sol[2][maxg];
int c[maxn], w[maxn];
int n, g;

int main()
{
	ifstream in ("rucsac.in");
	ofstream out ("rucsac.out");
	in>>n>>g;

	for (int i = 1; i <= n; i++) in>>w[i]>>c[i];

#if DEBUG==1
	// Print headers
	printf("\n               | ");
	for (int j = 0; j <= g; j++) {
		printf("%3d ", j);
	}

	printf("\n---------------+-");
	for (int j = 0; j <= g; j++) {
		printf("----");
	}

	// First row
	printf("\n      NONE     | ");
	for (int j = 0; j <= g; j++) {
		printf("%3d ", sol[0][j]);
	}

#endif

	for (int i = 1; i <= n; i++) {
		memcpy(sol[0], sol[1], sizeof(int) * (g + 2));

		for (int j = 1; j <= g; j++) {
			if (w[i] <= j) sol[1][j] = max(sol[0][j], sol[0][j - w[i]] + c[i]);
			else sol[1][j] = sol[0][j];
		}

#if DEBUG==1
		printf("\n(w:%3d; c:%3d) | ", w[i], c[i]);
		for (int j = 0; j <= g; j++) {
			printf("%3d ", sol[1][j]);
		}
#endif
	}

	out<<sol[1][g];
#if DEBUG==1
	printf("\n\nSolution: %d", sol[1][g]);
#endif

	in.close();
	out.close();
	return 0;
}