#include <cstdio>
#include <algorithm>
int main()
{
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);


	scanf("%d%d", &N, &G);
	for (int i = 1; i <= N; ++i)
		scanf("%d%d", &W[i], &P[i]);
	int l = 0;
	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]] 9+ P[i]);
		}

	Pmax = D[l][G];

	printf("%d\n", Pmax);
	return 0;
}