// Slower C++ solution:
#pragma once

#include <sstream>

#include <string>

#include <vector>

#include <map>

#include <algorithm>

#include <iostream>

#include <utility>

#include <set>

#include <cctype>

#include <queue>

#include <stack>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <deque>

#include <numeric>

#include <iomanip>

#define M_PI acos(-1)

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int INF = 1000000007;

const int MAX_V = 201;

int now = 0;



const int MAX = 510000;

const int MOD = 1000000007;



long long fac[MAX], finv[MAX], inv[MAX];



// テーブルを作る前処理

void COMinit() {

	fac[0] = fac[1] = 1;

	finv[0] = finv[1] = 1;

	inv[1] = 1;

	for (int i = 2; i < MAX; i++) {

		fac[i] = fac[i - 1] * i % MOD;

		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

		finv[i] = finv[i - 1] * inv[i] % MOD;

	}

}



// 二項係数計算

long long COM(int n, int k) {

	if (n < k) return 0;

	if (n < 0 || k < 0) return 0;

	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

}

struct edge {

	int t;

	ll cost;

	edge(int _t, ll _cost) : t(_t)

		, cost(_cost) {

	}

};



int n, k;



void Solve() {

	cin >> n >> k;

	pair<ll, ll> p[100010];

	ll kind = 0;

	ll sum = 0;

	set<ll> s;

	for (size_t i = 0; i < n; i++)

	{

		cin >> p[i].second >> p[i].first;

		if (!s.count(p[i].second)) kind++;

		s.insert(p[i].second);

		sum += p[i].first;

	}

	sort(p, p + n);

	ll red[100010];

	set<ll> s2;

	ll kind2 = 0;

	ll fd[100010];

	int pi = 0;

	int fi = 0;

	fd[fi++] = 0;

	for (int i = n - 1; i >= 0; i--)

	{

		if (!s2.count(p[i].second)) {

			kind2++;

			fd[fi++] = p[i].first + (kind2 * kind2 - (kind2 - 1) * (kind2 - 1));

			s2.insert(p[i].second);

		}

		else {

			red[pi++] = p[i].first;

		}

	}



	ll res = kind * kind + sum;

	for (size_t i = 0; i < n - k; i++)

	{

		ll fv = fd[fi - 1];

		if (pi > 0 & red[pi - 1] <= fv) {

			res -= red[--pi];

		}

		else { 

			res -= fv;

			fi--;

		}

	}

	cout << res << endl;

}

int main() {

	Solve();

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.4705058956698125x):
#pragma once

#include <stdio.h>

#include <sstream>

#include <string.h>

#include <vector>

#include <map>

#include <algorithm>

#include <iostream>

#include <utility>

#include <set>

#include <cctype>

#include <queue>

#include <stack>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <deque>

#include <limits>

#include <iomanip>

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

#define bit(x,v) ((ll)x << v)



const ll INF = 1000000007;

const ll MAX = 210000;

const ll MOD = 1000000007;



long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {

	fac[0] = fac[1] = 1;

	finv[0] = finv[1] = 1;

	inv[1] = 1;

	for (int i = 2; i < MAX; i++) {

		fac[i] = fac[i - 1] * i % MOD;

		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

		finv[i] = finv[i - 1] * inv[i] % MOD;

	}

}



// 二項係数計算

long long COM(int n, int k) {

	if (n < k) return 0;

	if (n < 0 || k < 0) return 0;

	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

}



ll gcd(ll a, ll b) {

	if (b == 0) return a;

	return gcd(b, a % b);

}

int pr[100010];

void uini(int n) {

	for (size_t i = 0; i <= n; i++)

	{

		pr[i] = i;

	}

}



int parent(int x) {

	if (x == pr[x]) return x;

	return pr[x] = parent(pr[x]);

}



bool unit(int x, int y) {

	int px = parent(x);

	int py = parent(y);



	if (px == py) return false;

	if (px < py) {

		pr[py] = px;

	}

	else {

		pr[px] = py;

	}

	return true;

}



// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)

vector<vector<int> > calcNext(const string & S) {

	int n = (int)S.size();

	vector<vector<int> > res(n + 1, vector<int>(26, n));

	for (int i = n - 1; i >= 0; --i) {

		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];

		res[i][S[i] - 'a'] = i;

	}

	return res;

}

// mod 1000000007 の世界で a += b する関数

void add(long long& a, long long b) {

	a += b;

	if (a >= MOD) a -= MOD;

}

const ll ainf = 998244353;

pair<ll,ll> sc[100010];



void solv() {



	ll n, k;

	cin >> n >> k;

	for (size_t i = 0; i < n; i++)

	{

		cin >> sc[i].second >> sc[i].first;

	}

	ll sum = 0;

	map<ll, int> mp;

	ll ki = 0;

	priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> >> q;

	for (size_t i = 0; i < n; i++)

	{

		sum += sc[i].first;

		mp[sc[i].second]++;

		if (mp[sc[i].second] == 1) ki++;

		q.push(sc[i]);

	}

	sum += ki * ki;

	

	int rem = n - k;

	ll t[100010];

	memset(t, 0, sizeof(t));

	priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> >> q2;



	while(rem > 0)

	{

                if(!q.empty()){

		pair<ll, ll> p = q.top();

		

		if (mp[p.second] == 1) {

                        q.pop();

			q2.push(p);

			mp[p.second]--;

			//ll po = pow(ki, 2) - pow(ki - 1,2);

			//p.first = po + (p.first - t[p.second]);

			//pair<ll, ll> p2 = q.top();

			//if (p2.first > p.first) {

			//	rem--;

			//	sum -= p.first;

			//	ki--;

			//	continue;

			//}

			//t[p.second] = po;

			//q2.push(p.first);

			continue;

		}

		if (!q2.empty()) {

			pair<ll, ll> p2 = q2.top();

			ll po = pow(ki, 2) - pow(ki - 1,2);

			if (po + p2.first < p.first) {

				rem--;

				sum -= po + p2.first;

				ki--;

				q2.pop();

				continue;

			}

		}

		sum -= p.first;

		mp[p.second]--;

		rem--;

                q.pop();

                }else{

pair<ll, ll> p2 = q2.top();

			ll po = pow(ki, 2) - pow(ki - 1,2);

			

				rem--;

				sum -= po + p2.first;

				ki--;

				q2.pop();

			



			

                 }

	}



	cout << sum << endl;



}



int main() {

	//COMinit();

	solv();



	return 0;

}