/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	// 入力
	ll N,K;
	cin >> N>>K;
	vector<P> vals; // pairの配列
	for (ll i = 0; i < N; ++i){
		ll t,d;
		cin>>t>>d; // ネタ種類番号, おいしさ
		t--; // 0はじまり
		vals.pb(make_pair(d,t)); // 要素追加 (おいしさ, ネタ番号)
	}
 
	// 解法
	sort(vals.begin(), vals.end(), greater<P>()); // 美味しさでソート
	
	ll map_count[N] = {0}; // 出現回数map
	ll value_list[N] = {0}; // おいしい順のおいしさの配列
	ll count_list[N] = {0}; // おいしい順の出現回数の配列
	REP(i,N){
		map_count[vals[i].second]++; // 出現回数カウントアップ
		value_list[i] = vals[i].first;
		count_list[i] = map_count[vals[i].second];
	}
	// REP(i,N) printf("i: %lld, value: %lld, count: %lld\n", i,value_list[i], count_list[i]);
	
	// 上からK個選ぶ
	vector<ll> not_unique_value; // 最初にK個選んだ集合の削除候補
	vector<ll> unique_value; // 最初のK個に選ばれなかった集合の追加候補
	ll num_type = 0; // 現段階の選んだ集合の種類数
	ll score = 0; // 現段階のスコア
	REP(i,N){ // 最初の集合、not_unique_list, unique_listの作成
		if (i<K){ // おいしい順にK個
			score += value_list[i];
			if (count_list[i]!=1) not_unique_value.pb(value_list[i]); // ユニークじゃないなら削除候補
			else num_type++;
		}
		else if (count_list[i]==1) unique_value.pb(value_list[i]); // ユニークなら追加候補
	}
	score += pow(num_type,2);
	ll ans = score;
	sort(not_unique_value.begin(), not_unique_value.end()); // 下り順にソート=>上から削除できる
	
	// 種類数を増やす
	ll i = 0;
	// printf("num type: %lld, score: %lld\n", num_type+i, score);
	while(num_type+i<K & i<unique_value.size()){
		score =   score - not_unique_value[i] + unique_value[i]
			    - pow(num_type+i,2) + pow(num_type+i+1,2);
		i++;
		// printf("num type: %lld, score: %lld\n", num_type+i, score);
		if (score>ans) ans = ll(score);
	}
	cout << ans << endl;
	
}

Measured memory_bytes: 5104