#include <fstream>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <cstring>
#include <map>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define oo 2000000
#define MOD 1000000007
using namespace std;

ifstream fin("a.in");
ofstream fout("a.out");
int dp[2][10005], w[5005], p[5005],n,G;
int main()
{
	fin >> n >> G;
	for (int i = 1; i <= n; i++)
	{
		fin >> w[i] >> p[i];
	}
	int lin = 0;
	dp[lin][w[1]] = p[1];
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= G; j++)
		{
			int M = dp[lin][j];
			if (j >= w[i] && M < dp[lin][j - w[i]] + p[i])
			{
				M = dp[lin][j - w[i]] + p[i];
			}
			dp[1 - lin][j] = M;
		}
		lin = 1 - lin;
	}
	int mx = 0;
	for (int i = 1; i <= G; i++)
	{
		mx = max(mx, dp[1][i]);
	}
	fout << mx;
}