#include <iostream>
#include <fstream>

std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");
int n, W, v[5001], w[10001];
int value[2][10001];

int main() {
	

	fin >> n >> W;
	for (int i = 1; i <= n; i++) {
		fin >> w[i] >> v[i];
	}
	for (int i = 0; i <= W; i++) value[0][i] = 0;

	for (int i = 1; i <= n; i++) {
		for (int cap = 0; cap <= W; cap++) {
			value[i%2][cap] = value[(i - 1) % 2][cap];
			if (cap >= w[i]) {
				if (value[i % 2][cap] < value[(i - 1) % 2][cap - w[i]] + v[i]) {
					value[i % 2][cap] = value[(i - 1) % 2][cap - w[i]] + v[i];
				}
			}
		}
	}
	fout << value[0][W];
}