#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<int>::iterator VII;

VI v[10];
int dp[2000];

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++){
		int c, g;
		scanf("%d %d", &c, &g);
		g--;
		
		v[g].push_back(c);
	}
	
	for (int i = 0; i < 10; i++){
		//for (VII it = v[i].begin(); it != v[i].end(); it++){
		//	for (int j = k; j > 0; j--){
		//		dp[j] = max(dp[j], dp[j - 1] + *it);
		//	}
		//}
		
		sort(v[i].begin(), v[i].end());
		reverse(v[i].begin(), v[i].end());
		
		for (int j = 1; j < v[i].size(); j++){
			v[i][j] += v[i][j - 1] + j * 2;
		}
		
		for (int j = k; j > 0; j--){
			for (int l = 0; l < v[i].size(); l++){
				if (j - l > 0)
					dp[j] = max(dp[j], dp[j - l - 1] + v[i][l]);
			}
		}
	}
	
	printf("%d\n", dp[k]);
	
	return 0;
}