#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 *a = malloc((maxW + 1) * sizeof(int));	//m[i-1][]
	int *b = malloc((maxW + 1) * sizeof(int));	//m[i][]
	int *aux;
	int g, it;

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

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

		aux = a;
		a = b;		//swap a[] and b[]
		b = aux;
	}

	int maxP = 0;
	for (g = 0; g <= maxW; g++)
		if (a[g] > maxP)
			maxP = a[g];

	return maxP;
}

int knapsack_On2_space(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;
}