/*---------------------*/
/*    books            */
/*    aoj0561          */
/*    dynamic program  */
/*---------------------*/

#include<bits/stdc++.h>
using namespace std;

int n,k;
vector<int> book[10];
int dp[10][2001];

int solve(int genre,int cnt);
int sum(int genre,int getnum);

int main(){
  memset(dp,-1,sizeof(dp));
  cin >> n >> k;
  for (int i = 0; i < n; i++){
    int a,b;
    cin >> a >> b;
    book[b-1].push_back(a);
  }
  for(int i = 0; i < 10; i++){
    sort(book[i].begin() , book[i].end() , greater<int>());
  }
  cout << solve(0,0) <<endl;
}

int solve(int genre,int cnt){
  if(genre == 10)return 0;
  if(dp[genre][cnt] != -1)return dp[genre][cnt];
  int rec = 0;
  for(int i = 0; i <= book[genre].size(); i++){
    if(cnt + i > k)break;
    rec = max(rec,solve(genre + 1,cnt + i) + sum(genre,i));
  }
  return dp[genre][cnt] = rec;
}

int sum(int genre,int getnum){
  int sum = 0;
  if(getnum == 0)return 0;
  for(int i = 0;i < getnum;i++){
    sum += book[genre][i];
  }
  return sum + (getnum - 1) * getnum;
}