#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[5001][10001];

int main(){

	int N, W;
	fin >> N >> W;
	int weights[N + 1], profits[N + 1];
	for(int i = 1; i <= N; ++i){
		fin >> weights[i] >> profits[i];
	}
	for(int i = 0; i <= N; ++i){
		for(int j = 0; j <= W; ++j){
			if(i == 0 || j == 0){
				dp[i][j] = 0;
			}
			else if(weights[i] <= j){
				dp[i][j] = max(dp[i - 1][j], profits[i] + dp[i - 1][j - weights[i]]);
			}
			else{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	fout << dp[N][W] << "\n";

	return 0;
}