#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

const int MAX_N=2000,MAX_G=10;
int N,K;
pair<int,int> book[MAX_N];	//first=G,second=C
int genre[MAX_G+1];
int genre2[MAX_G+1];	//????????????????????£???????????¬??????????????????
int table[MAX_G+1][MAX_N+1];
int dp[MAX_G+1][MAX_N+1];

void solve();

int main(){
	scanf("%d %d",&N,&K);
	for (int i=0;i<N;i++){
		int C,G;
		scanf("%d %d",&C,&G);
		book[i]=make_pair(G,C);
	}
	solve();
	return 0;
}

void solve(){
	sort(book,book+N);
	//table??????????????????
	int i,j,k;
	for (i=0;i<N;i++){
		genre2[book[i].first]++;
	}
	genre[1]=genre2[1];
	for (i=2;i<=MAX_G;i++){
		genre[i]=genre[i-1]+genre2[i];
	}
	for (i=1;i<=MAX_G;i++){
		for (j=genre[i]-1;j>=genre[i-1];--j){
			table[i][genre[i]-j]=table[i][genre[i]-j-1]+book[j].second;
		}
	}
	for (i=0;i<MAX_G;i++){
		//?????¨???????£?????????¨??????????????????
		for (j=2;j<=genre2[i+1];j++){
			table[i+1][j]+=j*(j-1);
		}
	}
	//???????¨?????????§?§£????±???????
	for (i=0;i<MAX_G;i++){
		for (j=0;j<=K;j++){
			for (k=0;k<=genre2[i+1] && j+k<=K;k++){
				dp[(i+1)][j+k]=max(dp[(i+1)][j+k],dp[i][j]+table[(i+1)][k]);
			}
		}
	}
	printf("%d\n",dp[MAX_G][K]);
}