#include <bits/stdc++.h>
#pragma warning(disable : 4996)

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

const int NMax = 5000;
const int GMax = 10000;

int n, g;
int w[NMax + 5];
int p[NMax + 5];

int mat[GMax + 5];

void dp(int n)
{
	for (int i = g; i >= 1; i--)
		if(i - w[n] >= 0)
			mat[i] = std::max(mat[i], mat[i - w[n]] + p[n]);
}

int main()
{
	fin >> n >> g;
	for (int i = 1; i <= n; i++)
		fin >> w[i] >> p[i];

	for(int i = 1; i <= n; i++)
		dp(i);

	fout << mat[g];
}