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

int rucsac(int weight[], int cost[], int n, int W){
	int dp[n+1][W+1];
	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){
				int aux = dp[i-1][cap-weight[i]] + cost[i];
				dp[i][cap] = max(dp[i][cap], aux);
			}
		}
	}

	return dp[n][W];
}

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

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