#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 = 0; wcrt <= G; wcrt++) {
			//fara i
			W[inc(l)][wcrt] = W[l][wcrt];

			if (w[i] <= wcrt) {
				//maximul dintre curent si daca am pune i
				W[inc(l)][wcrt] = max(W[inc(l)][wcrt], W[l][wcrt - w[i]] + p[i]);
			}
		}
	fout << W[l][G] << endl;
}