#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;


const string file = "rucsac";

const string infile = file + ".in";
const string outfile = file + ".out";



#define MAXN 5001
#define MAXG 10002

int N;
int G;

int W[MAXN];
int P[MAXN];

int Best[2][MAXG];
int Max;

void citire()
{
	fstream fin(infile.c_str(), ios::in);

	fin >> N >> G;

	for (int i = 0; i < N; i++)
	{
		fin >> W[i] >> P[i];
	}

	fin.close();

}


void solve()
{

	int first = 1;
	int second = 0;

	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j <= G; j++)
		{
			Best[second][j] = Best[first][j];
			if(j >= W[i])
			{
				Best[second][j] = max(Best[first][j], Best[first][j - W[i]] + P[i]);
			}
		}
		swap(first, second);
	}

	Max = Best[first][G];
}

void afisare()
{
	fstream fout(outfile.c_str(), ios::out);

	fout << Max << "\n";

	fout.close();
}


int main()
{
	citire();
	solve();
	afisare();

}