// https://infoarena.ro/problema/rucsac

#include <stdio.h>
#define NMAX 5005
#define GMAX 10005

int dp[2][GMAX];
int w[NMAX], p[NMAX];

int main()
{
	FILE* fin = fopen("rucsac.in", "r");
	FILE* fout = fopen("rucsac.out", "w");
	int n, g;
	fscanf(fin, "%d%d", &n, &g);

	for (int i = 1; i <= n; i++)
	{
		fscanf(fin, "%d%d", &w[i], &p[i]);
	}

	int c = 0;
	for (int i = 1; i <= n; c = 1 - c, i++)
	{
		for (int j = 0; j <= g; j++)
		{
			dp[1 - c][j] = dp[c][j];
			if (w[i] <= j)
				dp[1 - c][j] = (dp[1 - c][j] > dp[c][j - w[i]] + p[i]) ? dp[1 - c][j] : dp[c][j - w[i]] + p[i];
		}
	}

	fprintf(fout, "%d", dp[c][g]);
}