#pragma once
#include<iostream>
#include<fstream>
using namespace std;

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

#define dimN 5001
#define dimG 10001

int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main(){
	int N, G, profit = -1;
	fin >> N >> G;
	int greutati[dimN], valori[dimN], liniaCurenta[dimG], liniaPrecedenta[dimG]; // recurenta foloseste doar ce e cu un pas in spate, deci ajung 2 linii in loc de o matrice intreaga
	for (int i = 1; i <= N; i++)
		fin >> greutati[i] >> valori[i];
	for (int i = 0; i <= G; i++)
		liniaCurenta[i] = liniaPrecedenta[i] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= G; j++) {
			if (j >= greutati[i]) {
				liniaCurenta[j] = max(liniaPrecedenta[j], liniaPrecedenta[j - greutati[i]] + valori[i]);
				if (liniaCurenta[j] > profit)
					profit = liniaCurenta[j];
			}
		}
		for (int j = 0; j <= G; j++)
			liniaPrecedenta[j] = liniaCurenta[j];
	}

	fout << profit;
	return 0;
}