import std.stdio;
import std.algorithm;

void main() {
	long n, capacity;
	readf(" %s %s", &n, &capacity);

	auto weights = new long[n];
	auto values = new long[n];
	
	foreach (i;0..n) {
		readf(" %s %s", &weights[i], &values[i]);
	}

	auto dp = new long[][n + 1];
	foreach (ref e;dp) {
		e = new long[capacity + 1];
	}

	foreach (i;0..n) {
		foreach (j;0..capacity + 1) {
			if (j < weights[i]) {
				dp[i + 1][j] = dp[i][j];
			} else {
				dp[i + 1][j] = max(dp[i][j], dp[i][j - weights[i]] + values[i]);
			}
		}
	}

	writeln(dp[n][capacity]);
}
