#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int G = 11;
const int N = 2010;
const int K = N;

int calc(int g, int num, int val[][N])
{
  int sum = 0;
  for(int i = 0; i < num; ++i){
    sum += val[g][i];
  }
  return sum + num * (num-1);
}

int main()
{
  int n,k;
  while(cin>>n>>k){
    if(n==0&&k==0)break;
    
    static int val[G][N];
    static int dp[G][K];
    static int num[G] = {0,};

    for(int i = 0; i < n; ++i){
      int v,g;
      cin >> v >> g;
      val[g][num[g]] = v;
      num[g]++;
    }

    for(int g = 0; g < G; ++g){
      sort(val[g],val[g]+num[g]);
      reverse(val[g],val[g]+num[g]);
    }

    for(int i = 0; i < G; ++i){
      for(int j = 0; j <= k; ++j){
        dp[i][j] = 0;
      }
    }

    for(int g = 1; g < G; ++g){
      for(int i = 0; i <= k; ++i){
        for(int l = 0; l <= k; ++l){
          if( i-l < 0 ) break;
          if( l > num[g] ) break;
          dp[g+1][i] = max(dp[g+1][i], dp[g][i-l] + calc(g,l,val) );
        }
      }
    }

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