#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
vector<int> greutate,profit;
vector<vector<int>> dp;
int nr_obiecte, greutate_maxima, curent, ant;
int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

	f >> nr_obiecte >> greutate_maxima;
    greutate.resize(nr_obiecte+1);
	profit.resize(nr_obiecte+1);


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

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

	for (int i = 1; i <= nr_obiecte; i++)
		{   curent = i % 2;
		    ant = 1 - curent;
		    for (int j = 1; j <= greutate_maxima; j++)
                if(greutate[i]<=j)
                    dp[curent][j] = max(dp[ant][j], dp[ant][j - greutate[i]] + profit[i]);
                else
                    dp[curent][j] = dp[ant][j];
		}

		g<< dp[curent][greutate_maxima]<<'\n';
	return 0;
}