#include<bits/stdc++.h>
using namespace std;
int n,w;
struct nd{
	int w,v;
}it[3002];
long long dp[3002];
bool cmp(nd a,nd b)
{
	if(a.v==b.v)
	{
		return a.w<b.w;
	}
	return a.v<b.v;
}
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&it[i].w,&it[i].v);
	}
	sort(it+1,it+1+n,cmp);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		for(int j=it[i].w;j<=w;j++)
		{
			int nb=j/it[i].w;
			if(nb*it[i].v-nb*nb<0)
			{
				break;
			}else{
				dp[j]=max(dp[j],dp[j-nb*it[i].w]+nb*it[i].v-nb*nb);
			}
		}
	}
	cout<<dp[w];
	return 0;
}
/*
完全背包
选n件物品j时，贡献为n*v_j-n^2
每件物品重量为w_j 

*/

样例都过不了，转移方程错哪了