#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

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

int n,g,W[5002],P[5002],DP[10002];

int main(){
	fin>>n>>g;
	for(int i=1;i<=n;i++)
		fin>>W[i]>>P[i];
	for(int i=1;i<=n;i++)
		for(int j=g;j>=W[i];j--){
			DP[j]=max(DP[j],DP[j-W[i]]+P[i]);
		}
	fout<<DP[g];



	return 0;
}