#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 = 0; j < min(mw, v[i].w); j++) dp[t][j] = dp[!t][j];
		for (int j = v[i].w; j <= mw; j++)
			dp[t][j] = max(dp[!t][j], dp[!t][j-v[i].w]+v[i].p);
		
	}
	g << dp[!t][mw];

	return 0;
}