#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int v[5005];
pair <int, int> o[5005];
int n,Max,g;

int main(){
	fin>>n>>g;
	for(int i=0;i<n;i++)
		fin>>o[i].first>>o[i].second;
	for(int i=0;i<n;i++){
		for(int j=g;j>=o[i].first;j--){
			v[j]=max(v[j],v[j-o[i].first]+o[i].second);
			Max=max(Max,v[j]);
		}
	}
	fout<<Max;
	cout<<Max;
	return 0;
}