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

FILE *fin, *fout;

int maxProfit(std::vector<int> w, std::vector<int> p, int N, int G) {

	std::vector< std::vector<int> > dp(N + 1);

	for (int i = 0; i <= N; i++) {
		dp[i].resize(G + 1);
		dp[i][0] = 0;
	}

	for (int i = 0; i <= G; i++) {
		dp[0][i] = 0;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= G; j++) {
			dp[i][j] = dp[i - 1][j];

			if (j - w[i-1] >= 0) {
				dp[i][j] = std::max(dp[i][j], dp[i - 1][j - w[i - 1]] + p[i - 1]);
			}
		}
	}

	return dp[N][G];
}

int main(void) {
	int N, G, W, P;
	std::vector<int> w;
	std::vector<int> p;
	fin = fopen("rucsac.in", "r");
	fscanf(fin, "%d%d", &N, &G);
	
	for (int i = 0; i < N; i++) {
		fscanf(fin, "%d%d", &W, &P);
		w.push_back(W);
		p.push_back(P);
	}
	fclose(fin);

	fout = fopen("rucsac.out", "w");
	fprintf(fout, "%d", maxProfit(w, p, N, G));
	fclose(fout);
	return 0;
}