#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#ifndef U_L_LONG
typedef unsigned long long U_L_LONG;
#endif
#ifndef L_LONG
typedef long long L_LONG;
#endif

typedef std::pair<int, int> IntPair;


//static void ABC120D_DecayedBridges();
static void ABC116D_VariousSushi();


#if 1
int main()
{
	//ABC120D_DecayedBridges();
	ABC116D_VariousSushi();

	fflush(stdout);
	return 0;
}
#endif


class ABC116D_DataSet
{
public:
	int type = 0;
	int dPoint = 0;
	bool choose = false;
};

bool ABC116D_sortDsc(const ABC116D_DataSet& a, const ABC116D_DataSet& b)
{
	return (a.dPoint > b.dPoint);
}

static void ABC116D_VariousSushi()
{
	int N, K;
	static ABC116D_DataSet sushi[100001];
	static int sushiCountPerType[1000000] = { 0 };

	scanf(" %d %d", &N, &K);

	
	std::vector<std::vector<ABC116D_DataSet>> vData;
	vData.resize(N);

	for (int i = 0; i < N; i++) {
		scanf(" %d %d", &(sushi[i].type), &(sushi[i].dPoint));
		sushi[i].type--;		//	0-index で扱いたい
		sushiCountPerType[sushi[i].type]++;
	}

#if 1
	//	種類としては何種類か？
	int typeCount = 0;
	for (int i = 0; i < N; i++) {
		if (sushiCountPerType[i]) {
			typeCount++;
		}
	}
#endif

	std::sort(sushi, sushi + N, ABC116D_sortDsc);

	//	まずおいしさ基礎ポイント優先
	L_LONG dPointSum = 0;
	for (int i = 0; i < K; i++) {
		sushi[i].choose = true;
		vData[sushi[i].type].push_back(sushi[i]);
		dPointSum += sushi[i].dPoint;
	}

	L_LONG chkdTypes = 0;
	L_LONG tPointSum = 0;
	std::vector<int> vIdx;
	//	このときの種類ボーナスポイント集計
	for (int i = 0; i < N; i++) {
		if (vData[i].size()) {
			//	カウント済みの寿司は何種類か？
			chkdTypes++;
			if (vData[i].size() > 1) {
				vIdx.push_back(i);
			}
		}
	}
	tPointSum = chkdTypes * chkdTypes;

	L_LONG totalPointMax = dPointSum + tPointSum;
	
	if ((K >= N) || (chkdTypes == typeCount)) {
		printf("%lld\n", totalPointMax);
		return;
	}
	//	ここから種類優先に切り替えていく
	int sushiIdx = K;
	while (1) {
		L_LONG tmpMin = 2000000000LL;
		int rmvSushi = -1;
#if 0
		for (auto vType = vData.begin(); vType != vData.end(); vType++) {
			if (vType->size() > 1) {
				L_LONG typeMin = (vType->begin() + vType->size() - 1)->dPoint;

				if (tmpMin > typeMin) {
					tmpMin = typeMin;
					rmvSushi = vType->begin()->type;
				}
			}
		}
#else
		int atPos = 0;
		int idxSize = vIdx.size();
		for (int idx = 0; idx < idxSize; idx++) {
			if (vData[vIdx[idx]].size() > 1) {
				L_LONG typeMin = (vData[vIdx[idx]].begin() + vData[vIdx[idx]].size() - 1)->dPoint;
				if (tmpMin > typeMin) {
					tmpMin = typeMin;
					rmvSushi = vData[vIdx[idx]].begin()->type;
					atPos = idx;
				}
			}
		}
#endif
		if (rmvSushi < 0) {
			//	もう削れるところがない
			break;
		}

		while ((sushiIdx < N) && (vData[sushi[sushiIdx].type].size() > 0)) {
			sushiIdx++;
		}

		if (sushiIdx == N) {
			break;
		}
		else if (rmvSushi >= 0) {
			dPointSum -= tmpMin;
			vData[rmvSushi].erase(vData[rmvSushi].begin() + vData[rmvSushi].size() - 1);

			dPointSum += sushi[sushiIdx].dPoint;
			chkdTypes++;

			L_LONG tmpTotal = dPointSum + (chkdTypes * chkdTypes);
			if (totalPointMax < tmpTotal) {
				totalPointMax = tmpTotal;
			}

			if (chkdTypes == typeCount) {
				//	これ以上種類を増やす必要がなくなった
				break;
			}

			//	重複しないよう追加しておく
			vData[sushi[sushiIdx].type].push_back(sushi[sushiIdx]);

			if (vData[rmvSushi].size() <= 1) {
				//	いらないインデックスは消す
				vIdx.erase(vIdx.begin() + atPos);
			}

			sushiIdx++;
		}
	}

	printf("%lld\n", totalPointMax);
}


Measured memory_bytes: 8448