#include <cstdio>
#define max(a, b) a >= b ? a : b

using namespace std;

int n, g, w[5005], p[5005], d[5005][10005];

int main()
{
	FILE *in, *out;
	in = freopen("rucsac.in", "r", stdin);
	out = freopen("rucsac.out", "w", stdout);

	scanf("%i%i", &n, &g);
	for (int i = 1; i <= n; ++i) scanf("%i%i", &w[i], &p[i]);
	fclose(in);

	for (int i = 1; i <= n; ++i)
		for (int cw = 0; cw <= g; ++cw) {
			d[i][cw] = d[i - 1][cw];
			if (w[i] <= cw) d[i][cw] = max(d[i][cw], d[i - 1][cw - w[i]] + p[i]);
		}

	printf("%i", d[n][g]);
	fclose(out);

    return 0;
}