#include <iostream>
#include <fstream>
#define MAXN 5001
#define MAXG 10001

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N, G;
int weight[MAXN], price[MAXN];


void read() {
	f >> N >> G;
	for (int i = 1; i <= N; ++i) { 
		f >> weight[i] >> price[i];
	}
}
int knapsack() {
	int dp[MAXN][MAXG] = {0};
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= G; ++j) {
			if (j - weight[i] >= 0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + price[i]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	return dp[N][G];
}
int knapsack_efficient() {
	int dp[MAXG] = {0};
	for (int i = 1; i <= N; ++i) {
		for (int j = G; j >= 1; --j) {
			if (j - weight[i] >= 0) {
				dp[j] = max(dp[j], dp[j - weight[i]] + price[i]);
			}
		}
	}
	return dp[G];
}
 int main() {
	read();
	g << knapsack_efficient();

	return 0;
}