#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 5006
#define MOD 1999999973 
#define INF 2123456789
//#define fin cin 
//#define fout cout 

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

int n, G;
int v[nmax], g[nmax];
int dp[nmax][2 * nmax];

int main()
{
	int i, j, maxi;
	fin >> n >> G;
	for (i = 1; i <= n; i++)
		fin >> g[i] >> v[i];
	dp[1][g[1]] = v[1];
	for (i = 2; i <= n; i++)
		for (j = 1; j <= G; j++)
			if (j >= g[i])
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - g[i]] + v[i]);
			else
				dp[i][j] = dp[i - 1][j];
	maxi = 0;
	for (i = 1; i <= G; i++)
		maxi = max(maxi, dp[n][i]);
	fout << maxi << "\n";
	fin.close();
	fout.close();
	return 0;
}