#include <fstream>
#include <vector>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n, w;
vector<int> greutate, valoare;
vector<vector<int>> dp;

int main()
{
	cin >> n >> w;
	dp.resize(n + 1), greutate.resize(n + 1), valoare.resize(n + 1);
	dp[0].resize(w + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> greutate[i] >> valoare[i];
		dp[i].resize(w + 1);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= w; j++)
		{
			if (j - greutate[i] >= 0)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - greutate[i]] + valoare[i]);
			else
				dp[i][j] = dp[i - 1][j];
			
		}
		
	}
	cout << dp[n][w];
}