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

using namespace std;

long long int n, g, sol, w[5010], p[5010], d[5010][10010];

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

	scanf("%lld%lld", &n, &g);
	for (int i = 1; i <= n; ++i) scanf("%lld%lld", &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]);
		}

    sol = d[n][g];

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

    return 0;
}