#include <bits/stdc++.h>
using namespace std;
#define REP(i,x) for(int i = 0;i < x;++i)
#define ALL(a) (a).begin(),(a).end()

int n,k;
int c[2345],g[2345];

vector<int>bigst[10];
vector<int>accum[10];

const int INF = 123456789;
int memo[2345][11];
int dp(int i,int j)
{
	if(j == 0)
	{
		return (i == 0) ? 0 : -INF;
	}
	if(memo[i][j] >= 0)return memo[i][j];
	int lim = min((int)bigst[j-1].size(),i);
	int ans = 0;
	for(int x = 0;x <= lim;++x)
	{
		int fst = dp(i - x,j - 1);
		ans = max(ans,accum[j-1][x] + x * (x - 1) + fst);
	}
	return memo[i][j] = ans;
}

int main()
{
	cin >> n >> k;
	REP(i,n)
	{
		cin >> c[i] >> g[i];
		g[i]--;
		bigst[g[i]].push_back(c[i]);
	}
	REP(i,10)
	{
		sort(ALL(bigst[i]),[](const int&i1,const int&i2){return i1 > i2;});
		accum[i].push_back(0);
		for(int& val : bigst[i])
		{
			accum[i].push_back(accum[i].back() + val);
		}
	}
	memset(memo,0xff,sizeof(memo));
	int ans = dp(k,10);
	cout << ans << endl;
	return 0;
}