#include <bits/stdc++.h>

using namespace std;

int dp[2][10001];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int main(){
	
	int N, W;
	fin >> N >> W;
	int weights[N + 1], profits[N + 1];
	weights[0] = 0;
	profits[0] = 0;
	for(int i = 1; i <= N; ++i){
		fin >> weights[i] >> profits[i];
	}
	for(int i = 0; i <= N; ++i){
		if(i % 2){
			for(int j = 0; j <= W; ++j){
				if(weights[i] <= j){
					dp[1][j] = max(dp[0][j], dp[0][j - weights[i]] + profits[i]);
				}
				else{
					dp[1][j] = dp[0][j];
				}
			}
		}
		else{
			for(int j = 0; j <= W; ++j){
				if(weights[i] <= j){
					dp[0][j] = max(dp[1][j], dp[1][j - weights[i]] + profits[i]);
				}
				else{
					dp[0][j] = dp[1][j];
				}
			}
		}
	}
	fout << (N % 2 != 0)? dp[0][W]: dp[1][W];

	return 0;
}