// Original C++ solution (slower):
#include <bits/stdc++.h>



#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)

#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)

#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)

#define all(c) (c).begin(),(c).end()

#define sz(v) (int)(v).size()



using namespace std;

typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;

void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

template <class T> void amin(T& a,T b){ a=min(a,b);}

template <class T> void amax(T& a,T b){ a=max(a,b);}



int main()

{

	//cin.tie(0); ios_base::sync_with_stdio(false);

	int k,n;

	cin >> n >>k;

	VI d(n), t(n);

	rep(i,n) cin >>t[i] >>d[i];

	vector<VI> dt(100050);

	{

		vector<pii> vp(n);

		rep(i,n) vp[i] = pii(d[i], t[i]);

		sort(vp.rbegin(), vp.rend());

		rep(i,n){

			tie(d[i], t[i])=vp[i];

			dt[t[i]].push_back(i);

		}

	}

	vector<bool> usd(100050), uss(100050);

	VI dels, tsp;

	ll cnd=0; set<int> br;

	rep(i, k){

		cnd += d[i];

		uss[t[i]] = usd[i] = 1;

		if(dt[t[i]][0] !=i) dels.push_back(i);

	}

	ll zz=0;

	rep(i,100050) zz += uss[i]==1;

	cnd += (ll)zz *zz;

	//dbg("1stcnz",cnd,zz);

	ll ans = cnd;

	sort(all(dels),[&d](int a,int b){return d[a]<d[b];});

	rep(i,100050) if(sz(dt[i])>0) tsp.push_back(dt[i][0]);

	sort(all(tsp),[&d](int a,int b){return d[a]>d[b];});

	

	int dlc=-1, adc=-1;

	while(1){

		bool ck=0;

		rep2(i, dlc+1, sz(dels)) if(usd[dels[i]]){dlc=i; ck=1; break;}

		if(!ck) break;

		ck=0;

		rep2(i, adc+1, sz(tsp))  if(usd[tsp[i]]==0 && uss[t[tsp[i]]]==0){

			adc=i; ck=1; break;

		}

		if(!ck) break;

		cnd -= d[dels[dlc]]; usd[dels[dlc]]=0;

		cnd += d[tsp[adc]]; usd[tsp[adc]] =1;

		cnd -= zz*zz;

		zz++; cnd +=zz*zz;

		//dbg(cnd,zz);

		ans = max(ans, cnd);

	}

	cout << ans <<"\n";

	return 0;

}






// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)

#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)

#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)

#define all(c) (c).begin(),(c).end()

#define sz(v) (int)(v).size()



using namespace std;

typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;

void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

template <class T> void amin(T& a,T b){ a=min(a,b);}

template <class T> void amax(T& a,T b){ a=max(a,b);}



int main(){

	//cin.tie(0); ios_base::sync_with_stdio(false);

	const int MXZ=100050;

	int k,n;

	cin >> n >>k;

	VI d(n), t(n), dt(MXZ, -1);

	rep(i,n) cin >>t[i] >>d[i];

	{

		vector<pii> vp(n);

		rep(i,n) vp[i] = pii(d[i], t[i]);

		sort(vp.rbegin(), vp.rend());

		rep(i,n){

			tie(d[i], t[i])=vp[i];

			if(dt[t[i]]<0) dt[t[i]]=i;

		}

	}

	vector<bool> usd(MXZ), uss(MXZ);

	priority_queue<pii> pdel, padd;

	ll cnd=0;

	rep(i, k){

		cnd += d[i];

		uss[t[i]] = usd[i] = 1;

		if(dt[t[i]] !=i) pdel.push(pii(-d[i], i));

	}

	ll wz=0;

	rep(i,MXZ) wz += uss[i]==1;

	cnd += wz * wz;

	//dbg("1stcnz",cnd,wz);

	ll ans = cnd;

	for(int q: dt) if(q>=0 && !usd[q]) padd.push(pii(d[q], q));

	

	while(1){

		int dlc=-1, adc=-1;

		while(!pdel.empty() && dlc<0){

			auto p1= pdel.top().second; pdel.pop();

			if(usd[p1]) dlc = p1;

		}

		while(!padd.empty() && adc<0){

			auto p1= padd.top().second; padd.pop();

			if(!usd[p1] && !uss[t[p1]]) adc =p1;

		}

		if(dlc<0 || adc<0) break;

		

		cnd -= d[dlc]; usd[dlc]=0;

		cnd += d[adc]; usd[adc] =uss[t[adc]]=1;

		cnd += (wz+1)*(wz+1) - wz*wz;

		wz++; 

		//dbg(cnd,wz);

		ans = max(ans, cnd);

	}

	cout << ans <<"\n";

	return 0;

}

// Fastest known solution for this problem: