#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, K, dp[2001];
  vector< int > Book[10];
  cin >> N >> K;
  for(int i = 0; i < N; ++i){
    int C, G;
    cin >> C >> G;
    Book[G - 1].push_back(C);
  }
  fill_n( dp, K + 1, -1);
  dp[0] = 0;
  for(int i = 0; i < 10; ++i){
    sort(Book[i].rbegin(), Book[i].rend());
    for(int j = K - 1; j >= 0; --j){
      if(dp[j] == -1) continue;
      int sum = 0;
      for(int k = 0; k < Book[i].size() && j + k + 1 <= K; k++){
        sum += Book[i][k];
        dp[j + k + 1] = max( dp[j + k + 1], dp[j] + sum + (k + 1) * k);
      }
    }
  }
  cout << dp[K] << endl;
}