#include <fstream>
#define MAX(a, b) (((a)>(b)?(a):(b)))

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

int dp[G];

int main() {
	std::ifstream fin("rucsac.in");
	std::ofstream fout("rucsac.out");
	int n, g, a, b, ans = 0;
	fin>>n>>g;
	for(int i=1;i<=n;i++) {
		fin>>a>>b;
		for(int j=g-a;j>=0;j--){
			dp[j+a] = MAX(dp[j+a], dp[j] + b);
			ans = MAX(ans, dp[j+a]);
		}
	}
	fout<<ans;
}