#include <stdio.h>
#include <stdlib.h>

/* return maximum profit
 * s.t. total weight does not exceed maxW */
int knapsack(int n, int maxW, int* w, int* p) {
	int m[n][maxW + 1];	//m[i][w] - maximum profit for weight w (*exactly*) and items up to i
	int g, i, j;		//m[i][w] = max( m[i-1][w], m[i-1][w - w[i]] + p[i] )

	for (g = 0; g <= maxW; g++)
		m[0][g] = 0;
	m[0][w[0]] = p[0];

	for (i = 1; i < n; i++) {
		for (g = 0; g <= maxW; g++) {
			m[i][g] = m[i-1][g];
			if (w[i] <= g &&
					m[i-1][g-w[i]] + p[i] > m[i][g])
				m[i][g] = m[i-1][g-w[i]] + p[i];
		}
	}

	int maxP = 0;
	for (g = 0; g <= maxW; g++)
		if (m[n - 1][g] > maxP)
			maxP = m[n - 1][g];
	return maxP;
}

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

	int n, maxW; //n = num obj; maxW = max weight
	int *w, *p;	 //w = weight;  p = profit
	int i;

	scanf("%d %d", &n, &maxW);

	w = malloc(n * sizeof(int));
	p = malloc(n * sizeof(int));

	for (i = 0; i < n; i++) {
		scanf("%d %d", &w[i], &p[i]);
	}

	printf("%d", knapsack(n, maxW, w, p));

	free(w);
	free(p);
	return 0;
}