//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	int n, k; cin >> n >> k;

	//現在種類tの寿司が何個あるかメモする配列
	vector<int> f(n + 10);

	//とってないほう
	priority_queue<pair<LL,LL>> q;

	//とったほう
	//暫定的の解が入る
	priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> q2;
	
	//とりあえず美味しさの大きい順に取れるように
	//入力をプライオリティキューに突っ込んいく
	for (int i = 0; i < n; i++) {
		int t, d; cin >> t >> d;
		q.push(pair<LL, LL>(d, t));
	}

	//美味しさ大きい方からk個とる
	int co = 0;
	LL x = 0, s = 0, ans = 0;
	while (co < k) {
		pair<LL, LL> p = q.top(); q.pop();

		//暫定解を格納する配列へ移す
		q2.push(p);
		s += p.first;
		//はじめてでた種類のものだったら,種類数の合計をインクリメント
		if (f[p.second] == 0)x++;

		//そうでなくても、きちんとメモしておく。
		f[p.second]++;

		//いま何回足したか(この行いらない気がする)
		co++;
	}

	//貪欲に撮ったときの解をメモ
	ans = s + x * x;

	//まだいじってない寿司から交換して、解をよくしていくことを考える
	//種類を増やして解を良くできるか(これが大前提)
	//種類が減る方向にいっても、貪欲より良くならない!!!!
	while (!q.empty()) {

		//暫定解に入ってない寿司から最強の寿司をとってくる
		pair<LL, LL> p = q.top(); q.pop();

		//種類がダブったら、種類増えないので更新は起きない
		if (f[p.second])continue;

		//取り除く値兼フラグ
		LL m = -1;
		while (!q2.empty()) {

			//暫定解の中から一番弱いものをとってくる
			//暫定階の中で一番弱いものは、その種類の中でも一番弱い
			pair<LL, LL> p2 = q2.top(); q2.pop();

			//その種類が1個しかなかったら省かない
			//1個しかない寿司を省くと,種類が減ってしまうため
			if (f[p2.second] > 1) {

				//ダブってる中で一番弱いものを省く

				f[p2.second]--;
				m = p2.first;
				break;
			}
		}

		//種類が増えるように取れなかったら、更新は起きないので探索終了
		if (m == -1)break;

		//ここまできたら当然1種類増える
		x++;

		//加えた種類をメモする
		f[p.second]++;

		//値も足して
		s += p.first;

		//引く
		s -= m;

		//現在の素点と種類ボーナスの計算をして、更新
		ans = max(ans, s + x * x);
	}

	//出力
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5232