#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct chestie
{
	int g, c;
};
int n,m;
chestie v[505];
long long dp[505][505];

void citire()
{
	f >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		f >> v[i].g >> v[i].c;
	}
}

//primesti 10 pct
int rezolvare(int i, int g)
{
	if (i > n)
	{
		return 0;
	}
	int luam = 0;
	int nu_luam = 0;
	if (g - v[i].g >= 0)
	{
		luam = rezolvare(i+1, g - v[i].g) + v[i].c;
	}
	nu_luam = rezolvare(i + 1, g);

	return max(luam, nu_luam);
}

void rez()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (v[i].g <= j && v[i].c + dp[i - 1][j - v[i].g] > dp[i - 1][j])
			{
				dp[i][j] = v[i].c + dp[i - 1][j - v[i].g];
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
}
int main()
{
	citire();
	rez();
	g << dp[n][m];
}