#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define w first
#define p second

ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int N = 1005;
const int W = 10005;

int n, mw, t, dp[2][W];
pii v[N];

int main()
{
	f >> n >> mw;
	for (int i = 1; i <= n; i++) 
		f >> v[i].w >> v[i].p;
	for (int i = 1; i <= n; i++, t = !t)
		for (int j = 1; j <= mw; j++){
			dp[t][j] = dp[!t][j];
			if (v[i].w <= j)
				dp[t][j] = max(dp[t][j], dp[!t][j-v[i].w]+v[i].p);
		}
	g << dp[!t][mw];

	return 0;
}