#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[10001];
long long dp[10001];
long long maxi = -1;
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 = m; j >= v[i].g; j--)
		{
			if (v[i].c + dp[j - v[i].g] > dp[j])
			{
				dp[j] = v[i].c + dp[j - v[i].g];
			}
			maxi = max(dp[j], maxi);
		}
	}
}
int main()
{
	citire();
	rez();
	g << maxi;
}