#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;

const int N = 5005;
const int G = 10005;

int n, g;
pair<int, int> obiecte[N];
int dp[2][G];

void citire()
{
	scanf("%d %d", &n, &g);

	int tmp1, tmp2;

	for(int i = 0; i < n; i++)
	{
		scanf("%d %d", &tmp1, &tmp2);
		obiecte[i] = make_pair(tmp1, tmp2);
	}
}

void solve()
{
	int currentLine = 1;
	int prevLine = 0;

	for(int i = 0; i < n; i++)	
	{
		for(int j = 0; j <= g; j++)
		{
			if(j - obiecte[currentLine].first >= 0)		
			{
				dp[currentLine][j] = dp[prevLine][j];
				int tmp = dp[prevLine][j - obiecte[i].first] + obiecte[i].second;
				if(tmp > dp[currentLine][j])
				{
					dp[currentLine][j] = tmp;
				}

				currentLine = currentLine;
			}
		}

		prevLine = currentLine;
		currentLine ^= 1;
	}
	
	printf("%d", dp[prevLine][g]);
}

int main()
{
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);

	citire();
	solve();
	
	return 0;
}