// Galatan Tudor - Liceul Teoretic "Ion Luca"
// Vatra Dornei, 23.08.2015

#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>

#define Max_N 5001
#define Max_G 10001
 
using namespace std;

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

int w[Max_N], p[Max_N];
int O[Max_G];

int N, G, i, sol, j;
int main() 
{
	f >> N >> G;
    	for (i=1; i<=N; i++)
        	f >> w[i] >> p[i];
    	O[0] = 0;
    	sol = 0;
	for (i=1; i<=N; i++)
        	for (j=G-w[i]; j>=0; j--)
		{
			if (O[j+w[i]] < O[j]+p[i])
			{
				O[j+w[i]] = O[j]+p[i];
				if (O[j+w[i]] > sol)
					sol = O[j+w[i]];
			}
		}
    g << sol;
    return 0;
}