#include<bits/stdc++.h>
using namespace std;
#define int long long
int memo[2222][10];
vector<int> v[10];
int dfs(int b,int c){
  //cout<<b<<" "<<c<<endl;
  if(c==10) return 0;
  if(~memo[b][c]) return memo[b][c];
  int res=dfs(b,c+1),tmp=0;
  for(int i=0;i<(int)v[c].size();i++){
    if(b-(i+1)<0) break;
    tmp+=v[c][i];
    res=max(res,(tmp+i*(i+1))+dfs(b-(i+1),c+1));
  }
  //cout<<b<<" "<<c<<" "<<res<<endl;
  return memo[b][c]=res;
}
signed main(){
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    int c,g;
    cin>>c>>g;
    v[g-1].push_back(c);
  }
  for(int i=0;i<10;i++) sort(v[i].rbegin(),v[i].rend());
  /*
  for(int i=0;i<10;i++){
    cout<<i<<":";
    for(int j=0;j<(int)v[i].size();j++) cout<<v[i][j]<<" ";
    cout<<endl;
  }
  */
  memset(memo,-1,sizeof(memo));
  cout<<dfs(k,0)<<endl;
  return 0;
}