#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int rucsac(vector<int>& weight, vector<int>& cost, int n, int W){
	vector<vector<int>> dp(n+1);
    for(int i = 0; i <= n; i++){
        dp[i].resize(W+1);
    }
	int aux;
	for(int cap = 0; cap <= W; cap++){
		dp[0][cap] = 0;
	}
	for(int i = 1; i <= n; i++){
		for(int cap = 0; cap <= W; cap++){
			dp[i][cap] = dp[i-1][cap];
			if(cap - weight[i] >= 0){
			    aux = dp[i-1][cap-weight[i]] + cost[i];
				dp[i][cap] = std::max(dp[i][cap], aux);
			}
		}
	}

	return dp[n][W];
}

int main(){
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n, W;
    vector<int> weight;
    vector<int> cost;
    weight.resize(n+1);
    cost.resize(n+1);
	fin >> n >> W;
	for(int i = 1; i <= n; i++){
		fin >> weight[i] >> cost[i];
	}

	fout << rucsac(weight, cost, n, W) <<'\n';
	return 0;
}