#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
int dp[12][2001];
int book[11][2001];
int kind[11] = { 0 };
int acc[11][2001];
int main() {
	int N, K;
	int c, g;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> c >> g;
		book[g - 1][kind[g - 1]++] = c;
	}
	for (int i = 0; i < 11; i++) {
		sort(book[i], book[i] + kind[i]);
		reverse(book[i], book[i] + kind[i]);
	}
	for (int i = 0; i < 11; i++) {
		acc[i][0] = 0;
		for (int j = 1; j <= kind[i]; j++) {
			acc[i][j] = acc[i][j - 1] + book[i][j - 1] + 2 * (j - 1);
		}
	}
	for (int i = 0; i <= K; i++) {
		if (0 < i&&i <= kind[0])dp[0][i] = acc[0][i];
		else dp[0][i] = 0;
	}

	for (int i = 1; i <= 11; i++) {
		for (int j = 0; j <= K; j++) {
			dp[i][j] = 0;
			for (int k = 0; k <= min(j, kind[i]); k++) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + acc[i][k]);
			}
		}
	}
	cout << dp[11][K] << endl;
	return 0;
}
