#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;

int n, k;
vector<int> books[11];
int dp[11][2001];
int main()
{
  //chap1
  for(int i = 1; i <= 10; i++)
    books[i].push_back(0);
  
  //chap2
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    int c, g;
    cin >> c >> g;
    books[g].push_back(c);
  }

  //chap3
  for(int i = 1; i <= 10; i++)
    sort(books[i].begin() + 1, books[i].begin() + books[i].size(), greater<int>());  
  
  //chap4
  for(int i = 1; i <= 10; i++)
    for(int j = 2; j < books[i].size(); j++)
      books[i][j] += books[i][j - 1] + 2 * (j - 1);

  //chap4
  for(int i = 1; i <= 10; i++)
    for(int j = 0; j <= k; j++)
      for(int sell = 0; sell + j <= k && sell < books[i].size(); sell++)
	dp[i][j + sell] = max(dp[i][j + sell], dp[i - 1][j] + books[i][sell]);

  cout << dp[10][k] << endl;
  return 0;
}