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

int knapsack[3][10001];

int main(){
	ifstream fin;
	ofstream fout;
	fin.open("rucsac.in");
	fout.open("rucsac.out"); 
	int m, n, q, a, b, w;
	int value[5001];
	int weight[5001];


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

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= w; ++j){
				knapsack[i%2==1][j] = knapsack[i%2==0][j];
				if(j >= weight[i])
					knapsack[i%2==1][j] = max(knapsack[i%2==0][j - weight[i]] + value[i], knapsack[i%2==0][j]);
		}

	fout << knapsack[n%2][w];

}