#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional> //sort(A,A.end(),greater<int>());???????????????
#include <queue>
#include <stack>
#include <vector>

#define INF 10 << 10

int dp[2048] = { 0 };

int main() {

	int n, k;
	cin >> n >> k;
	vector<int> cg[16],list[16];
	for (int i = 0; i < n; ++i) {
		int c, g;
		cin >> c >> g;
		cg[g].push_back(c);
	}
	for (int i =1; i <= 10; ++i) {
		if (cg[i].empty()) continue;
		sort(cg[i].begin(), cg[i].end(), greater<int>());
		list[i].push_back(cg[i][0]);
		for (int i2 = 1; i2 < cg[i].size(); ++i2) {
			int sum = 0, cnt = 0;
			for (int j = i2; j >= 0; --j) { sum += cg[i][j]; cnt++; }
			list[i].push_back(sum + (cnt - 1)*cnt);
		}
	}
	for (int i = 1; i <= 10; ++i) {
		if (list[i].empty()) continue;
		for (int j = k; j >= 0; --j) {
			for (int i2 = 0; i2 < list[i].size() && j - (i2 + 1) >= 0; ++i2) {
				dp[j] = max(dp[j - (i2+1)] + list[i][i2], dp[j]);
			}
		}
	}

	cout << dp[k] << endl;

	return 0;
}