#include <bits/stdc++.h>
using namespace std;

#define M 10005
#define N 5005

int dp[2][M];

int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n, G, j;
	pair <int, int> v[N];
	fin >> n >> G;
	for(int i = 1; i <= n; i++)
		fin >> v[i].first >> v[i].second;
	for(int i = 1; i <= n; i++)
		for(j = 0; j <= G; j++){
			if(j < v[i].first)
			dp[i % 2][j] = dp[(i - 1) % 2][j];
			else dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - v[i].first] + v[i].second);
	}
	fout << dp[n % 2][G];
	return  0;
}