#include <fstream>
std::ifstream cin("rucsac.in");
std::ofstream cout("rucsac.out");
#define maxn 5010
#define maxw 10010
inline int max(int a,int b){if(a>b)return a;return b;}
int n,weight;
int w[maxn],val[maxn];
int g[2][maxw];

int main()
{
	int i,cw;
	cin>>n>>weight;
	for(i=1;i<=n;++i)
		cin>>w[i]>>val[i];
	int l=0;
	for(i=1;i<=n;++i,l=1-l)
		for(cw=0;cw<=weight;++cw){
			g[1-l][cw]=g[l][cw];
			if(w[i]<=cw)
				g[1-l][cw]=max(g[1-l][cw],g[l][cw-w[i]]+val[i]);
		}
	cout<<g[l][weight];
	return 0;
}