#include<fstream>
#include<iostream>
#include<ctime>
using namespace std;

clock_t start=clock();

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

int N, G;
int W[5001];
int Pr[5001];
int P[3][10001];

int main()
{	int i, j;

	f>>N>>G;
	for(i = 0; i < N; i++)
		f>>W[i]>>Pr[i];

	for(j = W[1]; j <= G; j++)
		P[0][j] = Pr[0];
	for(i = 1; i < N; i++)
		for(j = W[i]; j <= G; j++)
			P[i % 2][j] = max(P[(i - 1) % 2][j], P[(i - 1) % 2][j - W[i]] + Pr[i]);
	g<<P[(N - 1) % 2][G];

    cout << 1.0*(clock()-start)/(1.0*CLOCKS_PER_SEC) << '\n';
    f.close();
    g.close();
    return 0;
}