#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int main() {
	int n, g;
	fin>>n>>g;
	vector<int> w(n+1), p(n+1);
	for(int i=1;i<=n;i++) {
		int a,b;
		fin>>a>>b;
		w[i] = a;
		p[i] = b;
	}
	vector<vector<int>> dp(n+1, vector<int>(g+1,0));
	for(int i=1;i<=n;i++) {
		for(int cap=0; cap<=g; cap++) {
			dp[i][cap] = dp[i-1][cap];

			if(cap - w[i] >= 0) {
				dp[i][cap] = max(dp[i][cap], dp[i-1][cap-w[i]] + p[i]);
			}
		}
	}
	fout<<dp[n][g]<<endl;
	return 0;
}