#include <bits/stdc++.h>
using namespace std;
int i,n,g,j,w[10002],p[10002],dp[5002][10002];
int main(){
	ifstream cin ("rucsac.in");
	ofstream cout ("rucsac.out");
	cin>>n>>g;
	for (i=1;i<=n;i++)
	 cin>>w[i]>>p[i];
	for (i=1;i<=n;i++)
	 for (j=1;j<=g;j++){
	 	dp[i][j]=dp[i-1][j];
	 	if (j-w[i]>=0 ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
	 }

cout<<dp[n][g];
	return 0;
}