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

using namespace std;

int n, g, l, sol, w[10002], p[10002], d[2][10002];

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

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

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

    sol = d[l][g];

	printf("%d", sol);
	fclose(out);

    return 0;
}