#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

typedef vector<int> vi;

int n, k;
int dp[2000];
vi v[10], sum[10];

int main() {
	cin >> n >> k;
	REP(i, n) {
		int a, b;
		scanf("%d %d", &a, &b);
		v[b - 1].push_back(a);
	}

	REP(i, 10)
		sort(v[i].begin(), v[i].end(), greater<int>());
	REP(i, 10) {
		sum[i].push_back(0);
		REP(j, v[i].size()) {
			sum[i].push_back(sum[i][j] + v[i][j] + j * 2);
		}
	}

	REP(i, 10) {
		for (int j = k; j >= 0; j--) {
			FOR(l, 1, sum[i].size()) {
				if (j - l < 0) continue;
				dp[j] = max(dp[j], dp[j - l] + sum[i][l]);
			}
		}
	}
	
	cout << dp[k] << endl;
	return 0;
}