#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cctype>
#include<vector>

using namespace std;
vector<int> book[10];
vector<int> yen[10];
int dp[11][2001];

int main(){
  int n,k;
  int c,g;
  int sum;
  int a=0;

  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++){
    scanf("%d %d",&c,&g);
    book[g-1].push_back(c);
  }


  for(int i=0;i<10;i++){
    sort(book[i].begin(),book[i].end(),greater<int>());
    sum=0;
    for(int j=0;j<book[i].size();j++){
      sum+=book[i][j];
      yen[i].push_back(sum+j*(j+1));
    }
  }

  for(int i=0;i<2000;i++)dp[0][i]=0;

  for(int i=0;i<10;i++){
    for(int j=0;j<yen[i].size();j++){
      a=i;
      for(int l=j;l<k;l++){
	/*
	if(i+1==2 && l+1==2){
	  printf("%d   ",dp[2][2]);
	  printf("[%d %d %d]",dp[i+1][l+1],dp[i][l+1],dp[i][l-j]+yen[i][j]);
	}
	*/
	dp[i+1][l+1]=max(max(dp[i+1][l+1],dp[i][l+1]),dp[i][l-j]+yen[i][j]);
	//	if(i+1==2 && l+1==2)printf("   %d\n",dp[2][2]);
      }
    }
  }

  /*
  for(int j=1;j<=k+1;j++) printf("%10d",j);
  puts("");
  for(int i=0;i<11;i++){
    for(int j=0;j<k+1;j++){
      printf("%10d",dp[i][j]);
    }
    printf("    ");
    for(int j=0;j<yen[i].size();j++){
      printf("%10d",yen[i][j]);
    }
    puts("");
  }
  */

  printf("%d\n",dp[a+1][k]);
}