#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

#define MXN 5005
#define MXG 10005


int n,g;
int w[MXN] , p[MXN];
int v[MXG];

int rucsac()
{
	for (int i = 0; i <= g; ++i)
		v[i] = -1; // necalculat
	int pmax = 0;
	v[0] = 0;  // costa 0 sa pun 0 kilograme
    for(int i = 1; i <= n; i++)
        for(int j = g; j >= w[i]; j--)
			if ( v[j - v[i]] != -1 && v[j - w[i]] + p[i] > v[j])
			{
				v[j] = v[j - w[i]] + p[i];
				pmax = max(pmax, v[j]);
			}
    return pmax;
}

int main()
{
    
    fin >> n >> g;
    for(int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
    fout << rucsac();
    fin.close();
    fout.close();
    return 0;
}