#include<stdio.h>

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

	int n,W, m[5001][10001] = { 0 }, w[5001] = { 0 }, v[10001] = { 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;
}