#include<iostream>
#include<vector>
#include<cassert>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

/*n
i =0 to 9
j = 0 to K
  k=0 to junle[i](é«ãæ¹ãã)
  kåå£²ããªã k*(k-1)åã®å©ç
*/

const int N = 2001;
int dp[10][N];
int solve(int n,int K,vector<int> in[10]){
  int tmp = 0;
  //ini
  rep(i,10)rep(j,K+1)dp[i][j] = 0;

  //prec
  rep(i,in[0].size()){
    tmp += in[0][i];
    int t = i+1;
    dp[0][i+1] = tmp + t*max(0,t-1);
  }

  //dp
  REP(i,1,10){
    rep(j,K+1){
      dp[i][j] = dp[i-1][j];
      int tmp = 0;
      rep(k,in[i].size()){
	int t = k + 1;
	tmp += in[i][k];
	if (j-(k+1) >= 0){
	  dp[i][j] = max(dp[i][j],dp[i-1][j-(k+1)] + tmp + t*max(0,t-1));
	}
      }
    }
  }
  return dp[9][K];
}

int main(){
  int n,k;
  while(cin>>n>>k){
    vector<int> in[10];
    rep(i,n){
      int a,b;
      cin>>a>>b;
      in[b-1].push_back(a);
    }
    rep(i,10)sort(in[i].begin(),in[i].end(),greater<int>());
    cout << solve(n,k,in) << endl;
  }
}