#include<stdio.h>

int max(int a, int b) {
	if (a > b)return a;
	else return b;
}
int main() {

	int n, W, m[5001][100001] = { 0 };
	int w[5001] = { 0 };
	int v[100001] = { 0 };
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);

	scanf("%d %d", &n, &W);
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &w[i], &v[i]);

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= W; j++)
			if (w[i] > j)
				m[i][j] = m[i - 1][j];
			else
				m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
	}
	/*
	for (int i = 0; i <= n; i++) {
	for (int j = 0; j <= W; j++)
	printf("%d ", m[i][j]);
	printf("\n");
	}
	*/
	printf("%d", m[n][W]);

	return 0;
}