///Problema rucsacului
#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;

int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
	int nr_obiecte, greutate_maxima;
	f >> nr_obiecte >> greutate_maxima;
	vector<int> greutate(nr_obiecte+1);
	vector<int> profit(nr_obiecte+1);


	for (int i = 1; i <= nr_obiecte; i++)
		f >> greutate[i] >> profit[i];

	vector<vector<int>>dp(nr_obiecte +1 , vector<int>(greutate_maxima+1));

	for (int i = 1; i <= nr_obiecte; i++)
		for (int j = 1; j <= greutate_maxima; j++)
		{
			if (j - greutate[i] >= 0)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - greutate[i]] + profit[i]);
			else
				dp[i][j] = dp[i - 1][j];
		}
		g<< dp[nr_obiecte][greutate_maxima]<<'\n';
	return 0;
}