#include<bits/stdc++.h>
using namespace std;
long long n,w;
long long v[3005],c[3005];
long long dp[9000005];
long long dp2[9000005];
long long k[3005];
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>c[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=v[i];j<=w;j++)
		{
			k[i]++;
			dp[j]=max(dp[j],dp2[j-v[i]*k[i]]+k[i]*c[i]-k[i]*k[i]);
		}
		for(int j=v[i];j<=w;j++)
		{
			dp2[j]=dp[j];
		}
	}
	cout<<dp[w];
	return 0;
}