#include <iostream>
#include <fstream>

#define GMAX 10000
#define NMAX 5000
#define inc(n) n==1?0:1
#define max(a,b) a>b?a:b
using namespace std;

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

int N, G, l;
int w[NMAX+1], p[NMAX+1], W[2][GMAX+1];

int main() {
	fin >> N >> G;
	for (int i = 1; i <= N; i++)
		fin >> w[i] >> p[i];
	for (int i = 1; i <= N; i++, l = inc(l))
		for (int wcrt = G; wcrt >= w[i]; wcrt--) {
				//W[l][crt] -> daca nu punem obiectul
				//w[l][wcrt-w[i]] + p[i] -> daca adaugam obiectul la o valoare anterioara
				W[inc(l)][wcrt] = max(W[l][wcrt], W[l][wcrt - w[i]] + p[i]);
		}
	fout << W[l][G] << endl;
}