// knapsack

#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

int main(){
	int n,k; scanf("%d%d",&n,&k);
	vector<int> genre[10];
	rep(i,n){
		int val,g; scanf("%d%d",&val,&g); g--;
		genre[g].push_back(val);
	}

	int dp[11][2001];
	rep(j,k+1) dp[0][j]=(j==0?0:-INF);
	rep(g,10){
		rep(j,k+1) dp[g+1][j]=dp[g][j];

		sort(genre[g].begin(),genre[g].end(),greater<int>());
		int sum=0;
		rep(i,genre[g].size()){
			sum+=genre[g][i];

			int val=sum+i*(i+1),cost=i+1;
			for(int j=k;j>=cost;j--) dp[g+1][j]=max(dp[g+1][j],dp[g][j-cost]+val);
		}
	}
	printf("%d\n",dp[10][k]);

	return 0;
}