#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<int> c[10];
int memo[10][5000];

int calc(int g, int b)
{
	int ret = 0;

	if(b == 0) return 0;
	if(g == 0) {
		for(int i = 0; i < b; ++i)
			ret += c[g][i];
		return ret;
	}

	if(memo[g][b] != -1)
		return memo[g][b];

	int sum = 0;

	ret = calc(g - 1, b);

	for(int i = 1; i <= b; ++i) {

		sum += c[g][i - 1];
		ret = max(ret, sum + calc(g - 1, b - i));	
	}

	return memo[g][b] = ret;
}


int main()
{
	memset(memo, -1, sizeof(memo));

	scanf("%d%d", &n, &k);
	for(int i = 0; i < 10; ++i) c[i].reserve(n);
	for(int i = 0; i < n; ++i) {
		int tc, tg;
		scanf("%d%d", &tc, &tg);
		c[tg - 1].push_back(tc);
	}

	for(int i = 0; i < 10; ++i) {

		sort(c[i].rbegin(), c[i].rend());
		for(int j = 1; j < c[i].size(); ++j)
			c[i][j] += (2 * (j + 1) - 2);
	}

	printf("%d\n", calc(9, k));
	

	return 0;
}