#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> b[10];
int dp[2][2001];
int max(int a,int b){return a>b?a:b;}
int main(){
	int n,m;
	int i,j,k;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		int c,g;
		scanf("%d %d",&c,&g);
		g--;
		b[g].push_back(c);
	}
	for(i=0;i<10;i++){
		sort(b[i].begin(),b[i].end());
		reverse(b[i].begin(),b[i].end());
	}
	for(i=0;i<=m;i++)dp[1][i]=0;
	for(i=0;i<10;i++){
		for(j=0;j<=m;j++){
			dp[i%2][j]=max(dp[i%2][j],dp[(i+1)%2][j]);
			int s=0;
			for(k=0;k<b[i].size();k++){
				if(j+k+1>m)break;
				s+=b[i][k];
				dp[i%2][j+k+1]=max(dp[i%2][j+k+1],dp[(i+1)%2][j]+s+k*(k+1));
			}
		}
	}
	printf("%d\n",dp[1][m]);
	return 0;
}