AtCoder Beginner Contest 116 - Various Sushi

There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i.
You are choosing K among these N pieces to eat.
Your "satisfaction" here will be calculated as follows:
 - The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
 - The base total deliciousness is the sum of the deliciousness of the pieces you eat.
 - The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.
You want to have as much satisfaction as possible.
Find this maximum satisfaction.

-----Constraints-----
 - 1 \leq K \leq N  \leq 10^5
 - 1 \leq t_i \leq N
 - 1 \leq d_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

-----Output-----
Print the maximum satisfaction that you can obtain.

-----Sample Input-----
5 3
1 9
1 7
2 6
2 5
3 1

-----Sample Output-----
26

If you eat Sushi 1,2 and 3:
 - The base total deliciousness is 9+7+6=22.
 - The variety bonus is 2*2=4.
Thus, your satisfaction will be 26, which is optimal.

Difficulty: MEDIUM

Starter code:

Solutions:
(N, K) = map(int, input().split())
menu_ = []
for i in range(N):
	(t, d) = map(int, input().split())
	menu_.append((t, d))
menu = sorted(menu_, key=lambda x: x[1], reverse=True)
neta = set()
duplicates = []
for m in menu[:K]:
	if m[0] in neta:
		duplicates.append(m[1])
	else:
		neta.add(m[0])
p = sum([d for (t, d) in menu[:K]]) + len(neta) ** 2
ans = p
for m in menu[K:]:
	if m[0] not in neta and duplicates:
		neta.add(m[0])
		duplicate = duplicates.pop()
		p += m[1] - duplicate + 2 * len(neta) - 1
		ans = max(ans, p)
print(ans)


(n, k) = map(int, input().split())
tds = []
for i in range(n):
	(t, d) = map(int, input().split())
	tds.append((d, t))
tds.sort(reverse=True)
cnt = k
hand = []
hand_throw = []
hs = {}
subs = []
rs = {}
v_t = {}
res = 0
for i in range(n):
	if cnt > 0:
		if tds[i][1] in hs:
			hs[tds[i][1]] += 1
			hand_throw.append(tds[i][0])
		else:
			hs[tds[i][1]] = 1
			hand.append(tds[i][0])
		cnt -= 1
		res += tds[i][0]
	elif not tds[i][1] in rs and (not tds[i][1] in hs):
		rs[tds[i][1]] = 1
		subs.append(tds[i][0])
	if not tds[i][1] in v_t:
		v_t[tds[i][1]] = 1
subs.sort()
v_hs = len(hs)
v_t = len(v_t)
res += pow(v_hs, 2)
final_res = res
while v_hs + 1 <= k and v_hs + 1 <= v_t:
	res += subs.pop() - hand_throw.pop() - pow(v_hs, 2) + pow(v_hs + 1, 2)
	final_res = max(final_res, res)
	v_hs += 1
print(final_res)


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	from math import floor, ceil
	(n, k) = map(int, input().split())
	td = [list(map(int, input().split())) for _ in range(n)]
	td.sort(reverse=True, key=lambda a: a[1])
	delicious = 0
	syurui = set()
	suteru = []
	for i in range(k):
		(t, d) = td[i]
		delicious += d
		if t in syurui:
			suteru.append(d)
		else:
			syurui.add(t)
	suteru.sort()
	neta = len(syurui)
	res = delicious + neta ** 2
	for i in range(k, n):
		(t, d) = td[i]
		if t in syurui:
			continue
		if len(suteru) == 0:
			print(res)
			return
		syurui.add(t)
		x = suteru.pop(0)
		delicious += d - x
		neta += 1
		res = max(res, delicious + neta ** 2)
	print(res)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
a = [[int(t) for t in input().split()] for d in range(N)]
a.sort(key=lambda x: x[1], reverse=True)
x = []
y = []
st = set()
for i in range(K):
	(t, d) = a[i]
	if t in st:
		x.append(d)
	else:
		y.append(d)
		st.add(t)
X = sum(x)
Y = sum(y)
V = len(y)
res = X + Y + V ** 2
for i in range(K, N):
	if not x:
		break
	(t, d) = a[i]
	if t in st:
		continue
	st.add(t)
	X -= x.pop()
	Y += d
	V += 1
	res = max(res, X + Y + V ** 2)
print(res)


import heapq as h
I = lambda : list(map(int, input().split()))
(n, k) = I()
z = [i * 2 + 1 for i in range(n)]
s = sorted([I() for _ in [0] * n], key=lambda x: -x[1])
q = []
v = T = A = 0
l = [0] * -~n
for (i, (a, b)) in enumerate(s):
	if i < k:
		if l[a]:
			h.heappush(q, b)
		else:
			T += z[v]
			v += 1
		l[a] = 1
		T += b
	elif l[a] ^ 1 and q:
		l[a] = 1
		T += b + z[v] - h.heappop(q)
		v += 1
	A = max(A, T)
print(A)


(N, K) = map(int, input().split())
lis = []
val = 0
ans = 0
s = set()
dub = []
for _ in range(N):
	lis.append(tuple(map(int, input().split())))
lis = sorted(lis, key=lambda x: x[1], reverse=True)
for (t, v) in lis[:K]:
	if t in s:
		dub.append(v)
	s.add(t)
	val += v
ans = val + len(s) ** 2
for (t, v) in lis[K:]:
	if len(dub) == 0:
		break
	if t in s:
		continue
	s.add(t)
	r = dub.pop()
	val += v - r
	ans = max(ans, val + len(s) ** 2)
print(ans)


import heapq
(N, K) = map(int, input().split())
L = []
for _ in range(N):
	(t, d) = map(int, input().split())
	heapq.heappush(L, (-d, t))
LL = []
sum = 0
used = set()
for i in range(K):
	(d, t) = heapq.heappop(L)
	if t in used:
		heapq.heappush(LL, (-d, t))
	used.add(t)
	sum += -d
ans = len(used) ** 2 + sum
while L and LL:
	(d, t) = heapq.heappop(L)
	if t not in used:
		used.add(t)
		(dd, _) = heapq.heappop(LL)
		sum = sum - dd + -d
		ans = max(ans, len(used) ** 2 + sum)
print(ans)


from collections import defaultdict
from heapq import heappop, heappush
(N, K) = map(int, input().split())
TD = []
for _ in range(N):
	TD.append(tuple(map(int, input().split())))
TD.sort(key=lambda x: x[1], reverse=True)
D = defaultdict(list)
T = [0] * (N + 1)
H = []
ans = [0]
for (i, td) in enumerate(TD):
	(t, d) = (td[0], td[1])
	if i == K:
		break
	T[t] += 1
	D[t].append(d)
	ans[0] += d
	if T[t] >= 2:
		heappush(H, (D[t].pop(), t))
		T[t] -= 1
cnt = sum((1 for c in T if c >= 1))
ans[0] += cnt ** 2
for i in range(K, N):
	if H:
		(t1, d1) = TD[i]
		if T[t1] == 0:
			(d2, t2) = heappop(H)
			ans.append(ans[-1] + d1 - d2 + 2 * cnt + 1)
			cnt += 1
			T[t1] += 1
	else:
		break
print(max(ans))


(n, k) = map(int, input().split())
td = sorted([list(map(int, input().split())) for i in range(n)], reverse=True, key=lambda x: x[1])
type = set()
L = []
Sum = 0
for x in td[:k]:
	Sum += x[1]
	if x[0] not in type:
		type.add(x[0])
	else:
		L.append(x[1])
L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
	if len(L) == 0:
		break
	if x[0] not in type:
		type.add(x[0])
		type_cnt += 1
		Sum = Sum - L.pop(0) + x[1]
		ans = max(ans, Sum + type_cnt ** 2)
print(ans)


(N, K, *L) = map(int, open(0).read().split())
S = sorted([(d, t) for (t, d) in zip(*[iter(L)] * 2)], reverse=True)
In = set()
C = X = 0
uni = []
dub = []
for (d, t) in S:
	if t not in In:
		In.add(t)
		uni.append(d)
		X += 1
		if X == K:
			break
	else:
		dub.append(d)
det = 0
C = X
for d in dub:
	if C < K:
		det += d
		C += 1
	elif uni[-1] + 2 * X - 1 <= d:
		uni.pop()
		X -= 1
		det += d
print(sum(uni) + det + X ** 2)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	(r, t) = map(int, input().split())
	a.append((t, r))
a.sort(reverse=True)
d = {}
cd = []
dp = 0
x = 0
for i in range(m):
	(z, c) = a[i]
	dp += z
	if c in d:
		cd.append(z)
	else:
		d[c] = z
		x += 1
cd.sort(reverse=True)
ans = dp + x ** 2
c = ans
for i in range(m, n):
	if len(cd) == 0:
		break
	(z, v) = a[i]
	if v in d:
		continue
	d[v] = z
	x += 1
	c = c - cd.pop() + z + 2 * x - 1
	if c > ans:
		ans = c
print(ans)


(N, K) = map(int, input().split())
dt = []
for i in range(N):
	(t, d) = map(int, input().split())
	dt.append((d, t))
dt.sort()
dt.reverse()
dic = {}
can_delete = []
dp = 0
x = 0
for i in range(K):
	(d, t) = dt[i]
	dp += d
	if t in dic:
		can_delete.append(d)
	else:
		dic[t] = d
		x += 1
can_delete.sort()
can_delete.reverse()
ans = dp + x * x
v = ans
for i in range(K, N):
	if len(can_delete) == 0:
		break
	(d, t) = dt[i]
	if t in dic:
		continue
	dic[t] = d
	x += 1
	v = v - can_delete.pop() + d + 2 * x - 1
	if v > ans:
		ans = v
print(ans)


import heapq
(n, k) = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
arr = sorted(arr, reverse=True, key=lambda x: x[1])
q = []
v = set()
s = 0
for (t, d) in arr[:k]:
	s += d
	if t in v:
		heapq.heappush(q, d)
	else:
		v.add(t)
s += len(v) ** 2
ans = s
for (t, d) in arr[k:]:
	if t not in v and len(q) != 0:
		z = heapq.heappop(q)
		s += d + 2 * len(v) + 1 - z
		v.add(t)
		ans = max(ans, s)
print(ans)


(n, k) = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])
ans = 0
s = set()
q = []
for i in range(k):
	ans += a[i][1]
	if a[i][0] in s:
		q.append(a[i][1])
	s.add(a[i][0])
ans += len(s) ** 2
k1 = k
ans1 = ans
while k1 < n and q:
	if a[k1][0] not in s:
		ans1 = ans1 + a[k1][1] - q.pop() - len(s) ** 2 + (len(s) + 1) ** 2
		ans = max(ans, ans1)
		s.add(a[k1][0])
	k1 += 1
print(ans)


(n, k) = map(int, input().split())
TD = [[] for i in range(n)]
for i in range(n):
	TD[i] = list(map(int, input().split()))
TD.sort(key=lambda x: x[1], reverse=True)
ans = 0
huku = []
su = set([])
for (i, j) in TD[:k]:
	ans += j
	if i in su:
		huku.append([i, j])
	su.add(i)
ans += len(su) ** 2
huku.sort(key=lambda x: x[1], reverse=True)
ansl = []
ansl.append(ans)
for (i, j) in TD[k:]:
	if i in su:
		continue
	elif huku == []:
		break
	else:
		temp = ansl[-1] + j - huku.pop()[1] + (len(su) + 1) ** 2 - len(su) ** 2
		su.add(i)
		ansl.append(temp)
print(max(ansl))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
(N, K) = rl()
td = [rl() for _ in range(N)]
from operator import itemgetter
key0 = itemgetter(0)
key1 = itemgetter(1)
td.sort(key=key1, reverse=True)
netas = set()
dup = []
for (t, d) in td[:K]:
	if t in netas:
		dup.append(d)
	else:
		netas.add(t)
score = len(netas) ** 2 + sum(map(key1, td[:K]))
ans = score
for (t, d) in td[K:]:
	if t not in netas and dup != []:
		netas.add(t)
		dup_ = dup.pop(-1)
		score += 2 * len(netas) - 1 + d - dup_
		ans = max(ans, score)
print(ans)


import heapq
(N, K) = map(int, input().split())
S = []
for i in range(N):
	(t, d) = map(int, input().split())
	heapq.heappush(S, (-d, t))
sum_d = 0
types = set()
surplus = []
for i in range(K):
	(_d, t) = heapq.heappop(S)
	sum_d += -_d
	if t in types:
		heapq.heappush(surplus, -_d)
	else:
		types.add(t)
len_types = len(types)
ans = sum_d + len_types * len_types
while S and surplus:
	(_d, t) = heapq.heappop(S)
	if t in types:
		continue
	types.add(t)
	removed_d = heapq.heappop(surplus)
	sum_d += -_d - removed_d
	len_types += 1
	ans = max(ans, sum_d + len_types * len_types)
print(ans)


(n, k) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab_s = sorted(ab, key=lambda x: x[1])
ab_r = list(reversed(ab_s))
t = [x[0] for x in ab_r]
d = [x[1] for x in ab_r]
t_set = len(set(t[:k]))
d_sum = sum(d[:k])
res = [t_set ** 2 + d_sum]
from collections import Counter
t_cou = Counter(t[:k])
dp = [0] * (n + 1)
j_old = k - 1
for i in t_cou:
	dp[i] = t_cou[i]
for i in range(k, n):
	t_new = ab_r[i][0]
	if dp[t_new] == 0:
		for j in range(j_old, -1, -1):
			t_old = ab_r[j][0]
			if dp[t_old] <= 1:
				pass
			else:
				dp[t_new] = 1
				dp[t_old] -= 1
				t_set += 1
				d_sum = d_sum - ab_r[j][1] + ab_r[i][1]
				res.append(t_set ** 2 + d_sum)
				j_old = j - 1
				break
			j_old = -1
print(max(res))


(N, K) = map(int, input().split())
dt = sorted((tuple(map(int, input().split()))[::-1] for _ in range(N)))[::-1]
a = []
s = set()
(ans, cur) = (0, 0)
for (i, (d, t)) in enumerate(dt, 1):
	if t in s:
		if i <= K:
			a.append(d)
			cur += d
	else:
		if i > K:
			if not a:
				break
			cur -= a.pop()
		cur += d
		s.add(t)
	ans = max(ans, len(s) ** 2 + cur)
print(ans)


(n, k) = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: -x[1])
dic = dict()
tr = list()
curd = 0
curt = 0
for (t, d) in l[:k]:
	curd += d
	if t not in dic:
		curt += 1
		dic[t] = d
	elif dic[t] < d:
		tr.append(dic[t])
		dic[t] = d
	else:
		tr.append(d)
ans = curt ** 2 + curd
tr.sort(reverse=True)
for (t, d) in l[k:]:
	if t in dic:
		continue
	if not tr:
		break
	curt += 1
	dic[t] = d
	curd += d - tr.pop()
	cur = curt ** 2 + curd
	if ans < cur:
		ans = cur
print(ans)


import sys

def input():
	return sys.stdin.readline()[:-1]
(N, K) = map(int, input().split())
s = [None] * N
for i in range(N):
	(t, d) = map(int, input().split())
	s[i] = (d, t)
s.sort(reverse=True)
l = [0] * N
d = 0
for i in s[:K]:
	l[i[1] - 1] += 1
	d += i[0]
c = 0
for i in l:
	if i:
		c += 1
a = d + c ** 2
h = K - 1
for i in s[K:]:
	if not l[i[1] - 1]:
		while h >= 0:
			if l[s[h][1] - 1] > 1:
				l[i[1] - 1] = 1
				l[s[h][1] - 1] -= 1
				c += 1
				d = d + i[0] - s[h][0]
				a = max(a, d + c ** 2)
				h -= 1
				break
			h -= 1
		else:
			break
print(a)


def main():
	(N, K) = list(map(int, input().split()))
	l = []
	for _ in range(N):
		(t, d) = list(map(int, input().split()))
		l.append((t, d))
	l.sort(key=lambda x: x[1], reverse=True)
	s = set()
	e = []
	t = 0
	for i in range(K):
		t += l[i][1]
		if l[i][0] in s:
			e.append(l[i])
		else:
			s.add(l[i][0])
	rl = [t + len(s) * len(s)]
	e.reverse()
	ei = 0
	for i in range(K, N):
		if l[i][0] in s:
			continue
		if ei >= len(e):
			break
		s.add(l[i][0])
		t -= e[ei][1]
		t += l[i][1]
		ei += 1
		rl.append(t + len(s) * len(s))
	return max(rl)
print(main())


(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for i in range(N)]
TD.sort(key=lambda x: x[1])
import heapq
hq = []
heapq.heapify(hq)
selected = set()
ans = 0
for _ in range(K):
	(t, d) = TD.pop()
	if t in selected:
		heapq.heappush(hq, d)
	else:
		selected.add(t)
	ans += d
ans += len(selected) ** 2
tmp = ans
while TD:
	(t, d) = TD.pop()
	if t in selected:
		continue
	selected.add(t)
	if len(hq) == 0:
		break
	tmp -= heapq.heappop(hq)
	tmp += d
	tmp += len(selected) * 2 - 1
	ans = max(ans, tmp)
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
(n, k) = map(int, input().split())
Sushi = [list(map(int, input().split())) for i in range(n)]
Sushi = sorted(Sushi, key=lambda x: x[1], reverse=True)
ans = 0
A = []
kind = set()
for (t, d) in Sushi[:k]:
	ans += d
	if t in kind:
		A.append(d)
	else:
		kind.add(t)
ans += len(kind) ** 2
tmp = ans
for (t, d) in Sushi[k:]:
	if not A:
		break
	if not t in kind:
		tmp += d - A.pop() + 2 * len(kind) + 1
		kind.add(t)
		ans = max(ans, tmp)
print(ans)


(N, K) = map(int, input().split())
td = [[int(a) for a in input().split()] for i in range(N)]
td = sorted(td, key=lambda x: -x[1])
ans = 0
eat = set([])
noteat = []
for (t, d) in td[:K]:
	ans += d
	if t not in eat:
		eat.add(t)
	else:
		noteat.append(d)
temp_result = ans + len(eat) ** 2
max_result = temp_result
for (t, d) in td[K:]:
	if not noteat:
		break
	if t not in eat:
		temp_result += 2 * len(eat) + 1
		temp_result += d - noteat.pop()
		eat.add(t)
		max_result = max(max_result, temp_result)
print(max_result)


import heapq
(N, K) = list(map(int, input().split()))
sushi = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)
eaten = [False] * N
(d1, d2) = ([0], [0])
for i in range(N):
	(t, d) = sushi[i]
	t -= 1
	if eaten[t]:
		d1.append(d1[-1] + d)
	else:
		eaten[t] = True
		d2.append(d2[-1] + d)
ans = 0
for i in range(1, K + 1):
	if K - i >= len(d1):
		continue
	if i >= len(d2):
		continue
	ans = max(ans, d1[K - i] + d2[i] + i ** 2)
print(ans)


(N, K, *L) = map(int, open(0).read().split())
L = L[::-1]
I = set()
X = 0
U = []
D = []
for (d, t) in sorted(zip(*[iter(L)] * 2))[::-1]:
	if t in I:
		D += (d,)
	elif X < K:
		I |= {t}
		U += (d,)
		X += 1
D += (0,)
i = K - X
while X and U[-1] + 2 * X - 1 <= D[i]:
	U.pop()
	X -= 1
	i += 1
print(sum(U + D[:i]) + X ** 2)


import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
(n, k) = map(int, input().split())
TD = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True, key=itemgetter(1))
L = [[] for _ in range(n + 1)]
P = []
a = 0
cnt = 0
F = [-float('inf')] * (n + 1)
B = 0
for (t, d) in TD[:k]:
	if B >> t & 1:
		heapq.heappush(P, d)
	else:
		B |= 1 << t
		a += 1
	cnt += d
F[a] = cnt
for i in range(a, n):
	if len(P) == 0:
		break
	while k < n and B >> TD[k][0] & 1:
		k += 1
	if k == n:
		break
	(t, d) = TD[k]
	B |= 1 << t
	F[i + 1] = F[i] - heapq.heappop(P) + d
ans = 0
for i in range(a, n + 1):
	ans = max(ans, F[i] + i * i)
print(ans)


(n, k) = map(int, input().split())
sushi = []
for i in range(n):
	sushi.append([])
for i in range(n):
	(t, d) = map(int, input().split())
	sushi[t - 1].append(d)
Max = []
Rest = []
v = 0
for i in sushi:
	if not i == []:
		Max.append(max(i))
		i.remove(max(i))
		for j in i:
			Rest.append(j)
		v = v + 1
Max.sort(reverse=True)
Rest.sort(reverse=True)
Max_s = []
Rest_s = [0]
Sum = 0
for i in Max:
	Sum = Sum + i
	Max_s.append(Sum)
Sum = 0
l_r = 0
for i in Rest:
	Sum = Sum + i
	Rest_s.append(Sum)
	l_r = l_r + 1
ans = 0
for i in range(1, min(k, v) + 1):
	if k - i <= l_r:
		temp = Max_s[i - 1] + Rest_s[k - i] + i ** 2
		if ans < temp:
			ans = temp
print(ans)


import heapq
from collections import Counter
inf = 10 ** 10
(n, k) = map(int, input().split())
dset = [[] for i in range(n)]
for i in range(n):
	(t, d) = map(int, input().split())
	dset[t - 1].append(d)
for dd in dset:
	if dd:
		dd.sort(reverse=True)
	else:
		dd.append(-inf)
dset.sort(key=lambda x: -x[0])
cur = 0
hq = []
for i in range(k):
	cur += dset[i][0]
	for d in dset[i][1:]:
		heapq.heappush(hq, -d)
for dd in dset[k:]:
	for d in dd:
		heapq.heappush(hq, -d)
ans = cur + k * k
for i in range(k - 1, -1, -1):
	v = dset[i][0]
	if hq:
		w = -heapq.heappop(hq)
	else:
		break
	if v < w:
		cur += w - v
	else:
		heapq.heappush(hq, -w)
	ans = max(ans, cur + i * i)
print(ans)


(n, k) = map(int, input().split())
sushi = sorted((list(map(int, input().split()))[::-1] for i in range(n)))[::-1]
s = set()
q = []
kiso = 0
for i in range(k):
	(d, t) = sushi[i]
	if t in s:
		q.append(d)
	else:
		s.add(t)
	kiso += d
ans = kiso + len(s) ** 2
i = k
while i < n and q:
	(d, t) = sushi[i]
	if t not in s:
		s.add(t)
		kiso += -q.pop() + d
		ans = max(ans, kiso + len(s) ** 2)
		continue
	i += 1
print(ans)


import sys
from collections import deque
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, k) = list(map(int, input().split()))
	TD = [list(map(int, input().split())) for _ in range(n)]
	TD.sort(key=lambda z: -z[1])
	TD_new = [[] for _ in range(n)]
	for (t, d) in TD:
		TD_new[t - 1].append([d, 0] if len(TD_new[t - 1]) else [d, 1])
	ALL = []
	for td in TD_new:
		ALL.extend(td)
	ALL.sort(reverse=True)
	que = deque(ALL)
	x = y = 0
	zero = []
	for _ in range(k):
		(d, ex) = que.popleft()
		x += d
		y += ex
		if ex == 0:
			heappush(zero, d)
	res = x + y ** 2
	while que:
		(d, ex) = que.popleft()
		if ex:
			if zero:
				x += d - heappop(zero)
				y += 1
				res = max(res, x + y ** 2)
			else:
				break
	print(res)

def __starting_point():
	resolve()
__starting_point()


import heapq
(n, k) = list(map(int, input().split()))
L = []
for i in range(n):
	(t, d) = list(map(int, input().split()))
	L.append([d, t])
L.sort()
ans = []
cur = [0] * n
heap = []
var = 0
for i in range(k):
	if cur[L[n - i - 1][1] - 1] == 0:
		ans.append(L[n - i - 1][0])
		cur[L[n - i - 1][1] - 1] = 1
		var += 1
	else:
		heapq.heappush(heap, L[n - i - 1])
temp = 0
for i in range(len(ans)):
	temp += ans[i]
for i in range(len(heap)):
	temp += heap[i][0]
temp += var ** 2
now = temp
for i in range(n - k):
	if len(heap) != 0:
		a = heapq.heappop(heap)
		if cur[L[n - k - i - 1][1] - 1] == 0:
			cur[L[n - k - i - 1][1] - 1] = 1
			now -= var ** 2
			now -= a[0]
			var += 1
			now += var ** 2
			now += L[n - k - i - 1][0]
			temp = max(temp, now)
		else:
			heapq.heappush(heap, a)
print(temp)


import sys

def main():
	input = sys.stdin.readline
	(n, k) = map(int, input().split())
	S = [tuple(map(int, input().split())) for _ in range(n)]
	S.sort(key=lambda x: -x[1])
	(y_1, y_0) = ([0], [0])
	st = set()
	for (t, d) in S:
		if t in st:
			y_0.append(y_0[-1] + d)
		else:
			st.add(t)
			y_1.append(y_1[-1] + d)
	max_sum = -1
	for i in range(1, k + 1):
		if k - i >= len(y_0):
			continue
		if i >= len(y_1):
			break
		max_sum = max(max_sum, y_0[k - i] + y_1[i] + i ** 2)
	print(max_sum)
	return
main()


(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: -x[1])
(l, r) = (td[:K], td[K:])
used_l = [0] * N
for i in range(K):
	used_l[l[i][0] - 1] += 1
remove = []
for i in range(K - 1, -1, -1):
	if used_l[l[i][0] - 1] >= 2:
		remove.append(l[i][1])
		used_l[l[i][0] - 1] -= 1
used_r = used_l.copy()
add = []
for i in range(N - K):
	if used_r[r[i][0] - 1] == 0:
		add.append(r[i][1])
		used_r[r[i][0] - 1] += 1
t = sum(used_l)
ans = t ** 2
for i in range(K):
	ans += l[i][1]
ref = ans
for i in range(min(len(remove), len(add))):
	ref += (t + 1) ** 2 - t ** 2 + add[i] - remove[i]
	t += 1
	ans = max(ans, ref)
print(ans)


from heapq import heappop, heappush
(N, K) = map(int, input().split())
table = []
for i in range(N):
	(t, d) = map(int, input().split())
	t = t - 1
	table.append((d, t))
table = sorted(table, reverse=True)
L = [0] * N
H = set()
W = []
ans = -1
num = 0
for i in range(K):
	(d, t) = table[i]
	L[t] += 1
	H.add(t)
	num += d
	if L[t] >= 2:
		heappush(W, (d, t))
ans = len(H) ** 2 + num
for i in range(K, N):
	(d, t) = table[i]
	L[t] += 1
	if L[t] >= 2:
		continue
	if len(W) == 0:
		continue
	(d1, t1) = heappop(W)
	H.add(t)
	num = num - d1 + d
	ans = max(ans, len(H) ** 2 + num)
print(ans)


(N, K) = map(int, input().split())
S = [[-float('inf')] for k in range(N)]
for k in range(N):
	(t, d) = map(int, input().split())
	S[t - 1].append(d)
top = []
hoka = []
for k in range(N):
	S[k].sort()
	top.append(S[k].pop())
	hoka += S[k]
top.sort(reverse=True)
hoka.sort(reverse=True)
T = [0 for k in range(N + 1)]
H = [0 for k in range(N + 1)]
(T[1], H[1]) = (top[0], hoka[0])
for k in range(2, N):
	T[k] = T[k - 1] + top[k - 1]
	H[k] = H[k - 1] + hoka[k - 1]
ans = 0
for k in range(1, K + 1):
	ans = max(ans, T[k] + H[K - k] + k ** 2)
print(ans)


(n, k) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])
num += len(kind) ** 2
ans = num
for i in range(k, n):
	if not changable:
		break
	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2 * len(kind) + 1 - changable.pop()
		kind.add(sushi[i][0])
		ans = max(ans, num)
print(ans)


import sys
read = sys.stdin.readline
(n, k) = list(map(int, read().split()))
sushi = [[] for _ in range(n)]
for i in range(n):
	(t, d) = list(map(int, read().split()))
	t -= 1
	sushi[t].append(d)
max_sushi = []
other_sushi = []
for i in range(n):
	if len(sushi[i]) == 0:
		continue
	sushi[i].sort()
	max_sushi.append(sushi[i][-1])
	for j in range(len(sushi[i]) - 1):
		other_sushi.append(sushi[i][j])
max_sushi.sort(reverse=True)
other_sushi.sort(reverse=True)
for i in range(len(max_sushi) - 1):
	max_sushi[i + 1] += max_sushi[i]
for i in range(len(other_sushi) - 1):
	other_sushi[i + 1] += other_sushi[i]
a = len(max_sushi)
b = len(other_sushi)
ans = 0
for x in range(1, k + 1):
	if x > a or k - x > b:
		continue
	other = 0 if k - x - 1 < 0 else other_sushi[k - x - 1]
	ans = max(ans, x * x + max_sushi[x - 1] + other)
print(ans)


(N, K) = [int(x) for x in input().split()]
td = [0] * N
for i in range(N):
	td[i] = [int(x) for x in input().split()]
td = sorted(td, reverse=True)
var_p1 = [0] * N
var_p0 = [0] * N
n_p1 = 0
n_p0 = 0
for i in range(N):
	if i == 0 or (i > 0 and td[i][0] != td[i - 1][0]):
		var_p1[n_p1] = td[i][1]
		n_p1 += 1
	else:
		var_p0[n_p0] = td[i][1]
		n_p0 += 1
var_p1.sort(reverse=True)
var_p0.sort(reverse=True)
val_taste = sum(var_p0[0:K])
val_vars = 0
ans = 0
for j in range(1, K + 1):
	val = var_p1[j - 1]
	if val <= 0:
		break
	val_taste = val_taste + val - var_p0[K - j]
	val_vars = j * j
	ans = max(ans, val_taste + val_vars)
print(ans)


(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
M = len(set([t for (t, d) in TD]))
TD.sort(key=lambda x: x[1], reverse=True)
(p, S, V) = (0, [], set())
for (t, d) in TD[:K]:
	p += d
	if t in V:
		S.append(d)
	else:
		V.add(t)
p += len(V) ** 2
ans = p
for (t, d) in TD[K:]:
	if len(S) == 0:
		break
	if t not in V:
		p += 2 * len(V) + 1 - S.pop() + d
		V.add(t)
		ans = max(ans, p)
print(ans)


from operator import itemgetter
(n, k) = map(int, input().split())
li = []
s = []
t = []
g = 0
ans = []
retu = [0] * n
p = 0
q = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	li.append([a, b])
li = sorted(li, key=itemgetter(1), reverse=True)
for i in range(k):
	g += li[i][1]
	if retu[li[i][0] - 1] == 0:
		retu[li[i][0] - 1] += 1
		p += 1
	else:
		t.append(li[i][1])
		q += 1
g += p ** 2
ans.append(g)
for i in range(k, n):
	if q == 0:
		break
	if retu[li[i][0] - 1] == 0:
		g = g - t[q - 1] + li[i][1] + 2 * p + 1
		p += 1
		q -= 1
		ans.append(g)
		retu[li[i][0] - 1] += 1
print(max(ans))


from heapq import heappush, heappop
(n, k) = list(map(int, input().split()))
td = [list(map(int, input().split())) for _ in range(n)]
td.sort(key=lambda x: x[1], reverse=True)
types = set()
can_remove = []
d_sm = 0
for (t, d) in td[:k]:
	d_sm += d
	if t in types:
		can_remove.append(d)
	else:
		types.add(t)
type_cnt = len(types)
ans = d_sm + type_cnt ** 2
left = []
for (t, d) in td[k:]:
	d = -d
	heappush(left, [d, t])
while can_remove and left:
	(d, t) = heappop(left)
	d = -d
	if t not in types:
		types.add(t)
		d_rmv = can_remove.pop()
		d_sm += d - d_rmv
		type_cnt += 1
		ans = max(ans, d_sm + type_cnt ** 2)
print(ans)


from heapq import heappush, heappop
(N, K) = map(int, input().split())
(t, d) = zip(*(map(int, input().split()) for _ in range(N))) if N else ((), ())
S = sorted(zip(d, t), reverse=True)
q = []
v = set()
s = 0
for (D, T) in S[:K]:
	s += D
	if T in v:
		heappush(q, D)
	else:
		v.add(T)
s += len(v) ** 2
opt = s
for (D, T) in S[K:]:
	if T not in v and q:
		z = heappop(q)
		s += D + 2 * len(v) + 1 - z
		v.add(T)
		opt = max(opt, s)
ans = opt
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
td.sort(key=lambda x: x[1], reverse=True)
base = []
other = []
val = set()
yum = 0
for (t, d) in td[:k]:
	yum += d
	if t in val:
		other.append(d)
	val.add(t)
other.sort(reverse=True)
kouho = []
val_tmp = val.copy()
for (t, d) in td[k:]:
	if t not in val_tmp:
		kouho.append(d)
		val_tmp.add(t)
kouho.sort()
v = len(val)
ans = yum + v * v
while len(other) > 0 and len(kouho) > 0:
	yum -= other.pop()
	yum += kouho.pop()
	v += 1
	ans = max(ans, yum + v * v)
print(ans)


(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda p: -p[1])
neta = set()
oisi = netan = 0
amari = []
for (t, d) in TD[:K]:
	oisi += d
	if t not in neta:
		neta.add(t)
		netan += 1
	else:
		amari.append(d)
ans = oisi + netan * netan
for (t, d) in TD[K:]:
	if netan == K or not amari:
		break
	if t not in neta:
		neta.add(t)
		netan += 1
		oisi += d - amari.pop()
		ans = max(ans, oisi + netan * netan)
print(ans)


import sys
input = sys.stdin.readline
(N, K) = list(map(int, input().split()))
nums = []
for i in range(N):
	(t, d) = list(map(int, input().split()))
	nums.append((d, t))
nums.sort(reverse=True)
se = set()
doubled = []
rest = []
points = 0
for (i, n) in enumerate(nums):
	if i < K:
		if not n[1] in se:
			se.add(n[1])
		else:
			doubled.append(n)
		points += n[0]
	else:
		rest.append(n)
ans = points + pow(len(se), 2)
idx = len(doubled) - 1
for (d, t) in rest:
	if idx < 0:
		break
	if t in se:
		continue
	points -= doubled[idx][0]
	idx -= 1
	points += d
	se.add(t)
	ans = max(ans, points + pow(len(se), 2))
print(ans)


def resolve():
	(N, K) = list(map(int, input().split()))
	TD = sorted([list(map(int, input().split())) for _ in range(N)], reverse=True, key=lambda x: x[1])
	eat_types = set()
	eat_dups = []
	total = 0
	for i in range(K):
		(typ, point) = TD[i]
		total += point
		if typ in eat_types:
			eat_dups.append(TD[i])
		else:
			eat_types.add(typ)
	ans = total + len(eat_types) ** 2
	didx = len(eat_dups) - 1
	for i in range(K, N):
		(typ, point) = TD[i]
		if typ in eat_types:
			continue
		if didx < 0:
			break
		total -= eat_dups[didx][1]
		total += point
		didx -= 1
		eat_types.add(typ)
		ans = max(ans, total + len(eat_types) ** 2)
	print(ans)
if '__main__' == __name__:
	resolve()


from collections import defaultdict as dd
from heapq import heappop, heappush
(N, K) = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda x: -x[1])
used = set()
q1 = dd(list)
(q2, q3) = ([], [])
(score, kind) = (0, 0)
for (t, d) in l[:K]:
	score += d
	if t in used:
		heappush(q3, d)
	else:
		used.add(t)
		kind += 1
for (t, d) in l[K:]:
	if not t in used:
		heappush(q1[t], -d)
for t in q1.keys():
	d = heappop(q1[t])
	heappush(q2, d)
ans = score + kind * kind
while q2 and q3:
	score -= heappop(q2) + heappop(q3)
	kind += 1
	ans = max(ans, score + kind * kind)
print(ans)


from heapq import heappush, heappop
(n, k) = map(int, input().split())
H = []
for i in range(n):
	(t, d) = map(int, input().split())
	heappush(H, (-d, t))
Q = []
used = {}
dsum = 0
for i in range(k):
	(d, t) = heappop(H)
	if t not in used:
		used[t] = 1
	else:
		heappush(Q, (-d, t))
	dsum += -d
ans = len(used) ** 2 + dsum
while H and Q:
	(d, t) = heappop(H)
	if t not in used:
		used[t] = 1
		(m, _) = heappop(Q)
		dsum = dsum - m - d
		ans = max(ans, len(used) ** 2 + dsum)
print(ans)


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
hq = []
(n, k) = map(int, input().split())
for i in range(n):
	(t, d) = map(int, input().split())
	heappush(hq, (-d, t))
D = 0
dic = {}
got = []
for i in range(k):
	r = heappop(hq)
	got.append(r)
	if r[1] in dic:
		dic[r[1]] += 1
	else:
		dic[r[1]] = 1
	D += -r[0]
ans = D + len(dic) ** 2
while hq:
	while got:
		p = got.pop()
		if dic[p[1]] > 1:
			dic[p[1]] -= 1
			D -= -p[0]
			break
	if len(got) == 0:
		print(ans)
		exit()
	r = heappop(hq)
	got.append(r)
	if r[1] in dic:
		dic[r[1]] += 1
	else:
		dic[r[1]] = 1
	D += -r[0]
	ans = max(D + len(dic) ** 2, ans)
print(ans)


(N, K) = map(int, input().split())
Sushi = [[int(i) for i in input().split()] for j in range(N)]
Sushi = sorted(Sushi, key=lambda x: x[1], reverse=True)
inp = {}
for (t, d) in Sushi:
	if not t in inp:
		inp[t] = d
tasty = 0
neta = set()
dup = []
for i in range(K):
	(t, d) = Sushi[i]
	tasty += d
	if t in neta:
		dup.append((t, d))
	neta.add(t)
	if t in inp:
		del inp[t]
variety = len(neta)
max_tasty = tasty + variety ** 2
for (s, t) in sorted(inp.items(), key=lambda x: x[1], reverse=True):
	if len(dup):
		(s1, t1) = dup.pop()
		variety += 1
		tasty = tasty - t1 + t
		max_tasty = max(max_tasty, tasty + variety ** 2)
print(max_tasty)


from collections import defaultdict
from heapq import heappush, heappop
(N, K, *L) = map(int, open(0).read().split())
dic = defaultdict(list)
ls = []
for (i, (t, d)) in enumerate(zip(*[iter(L)] * 2)):
	dic[t].append(d)
	heappush(ls, (-d, t))
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
	(d, t) = heappop(ls)
	ans -= d
	if t not in S:
		num += 1
		S.add(t)
	else:
		heappush(pre, -d)
ans += num * num
if pre == []:
	print(ans)
	return
m = ans
for i in range(N - K):
	(d, t) = heappop(ls)
	if t in S:
		continue
	S.add(t)
	m -= heappop(pre)
	m += -d + 2 * num + 1
	num += 1
	ans = max(ans, m)
	if pre == []:
		break
print(ans)


import sys
readline = sys.stdin.readline
(N, K) = map(int, readline().split())
from collections import defaultdict
sushi = defaultdict(list)
for i in range(N):
	(t, d) = map(int, readline().split())
	sushi[t].append(d)
best_sushi = []
other_sushi = []
for value in sushi.values():
	value = sorted(value, reverse=True)
	best_sushi.append(value[0])
	other_sushi += value[1:]
best_sushi = sorted(best_sushi, reverse=True)
other_sushi = sorted(other_sushi, reverse=True)
best_num = 1
other_num = K - 1
if len(other_sushi) < other_num:
	other_num = len(other_sushi)
	best_num = K - other_num
other_sushi = other_sushi[:other_num]
sushi_point = sum(best_sushi[:best_num]) + sum(other_sushi)
kind_point = best_num ** 2
ans = sushi_point + kind_point
for i in range(best_num, len(best_sushi)):
	sushi_point += best_sushi[i]
	if len(other_sushi) == 0:
		break
	rem = other_sushi.pop()
	sushi_point -= rem
	kind_point = (i + 1) ** 2
	if ans < sushi_point + kind_point:
		ans = sushi_point + kind_point
print(ans)


(n, k) = map(int, input().split())
TD = [list(map(int, input().split())) for _ in range(n)]
TD = sorted(TD, key=lambda x: -x[1])
q = []
ans = 0
v = set()
cnt = 0
for (t, d) in TD[:k]:
	ans += d
	if t in v:
		q.append(d)
	else:
		v.add(t)
ans += len(v) ** 2
cnt = ans
for (t, d) in TD[k:]:
	if t not in v and len(q) != 0:
		x = q.pop()
		ans += d + 2 * len(v) + 1 - x
		v.add(t)
		cnt = max(ans, cnt)
print(cnt)


(N, K) = [int(a) for a in input().split(' ')]
TD = [[int(a) for a in input().split(' ')] for i in range(N)]
TD = sorted(TD, key=lambda arr: arr[1])[::-1]
types = set()
stack = []
(ans, totald, i) = (0, 0, 0)
for i in range(K):
	(t, d) = TD[i]
	if t in types:
		stack.append(d)
	totald += d
	types.add(t)
ans = totald + len(types) ** 2
while len(stack) > 0:
	while i < N and TD[i][0] in types:
		i += 1
	if i >= N:
		break
	(t1, d1) = TD[i]
	lt = len(types)
	d2 = stack.pop()
	totald -= d2 - d1
	types.add(t1)
	i += 1
	ans = max(ans, totald + len(types) ** 2)
print(ans)


(N, K, *L) = map(int, open(0).read().split())
ls = []
for (i, (t, d)) in enumerate(zip(*[iter(L)] * 2)):
	ls.append((d, t))
ls.sort()
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
	(d, t) = ls.pop()
	ans += d
	if t not in S:
		num += 1
		S.add(t)
	else:
		pre.append(d)
pre.sort(reverse=True)
ans += num * num
if pre == []:
	print(ans)
	return
m = ans
for i in range(N - K):
	(d, t) = ls.pop()
	if t in S:
		continue
	S.add(t)
	m -= pre.pop()
	m += d + 2 * num + 1
	num += 1
	ans = max(ans, m)
	if pre == []:
		break
print(ans)


from heapq import heappop, heappush
INF = 10 ** 18
(N, K) = map(int, input().split())
S = [[] for _ in range(N)]
for _ in range(N):
	(t, d) = map(int, input().split())
	S[t - 1].append(d)
for i in range(N):
	S[i].sort(reverse=True)
	if not S[i]:
		S[i].append(-INF)
S.sort(reverse=True)
uma = 0
que = []
for i in range(K):
	uma += S[i][0]
	for j in range(1, len(S[i])):
		heappush(que, -1 * S[i][j])
for i in range(K, N):
	for j in range(len(S[i])):
		heappush(que, -1 * S[i][j])
ans = uma + K * K
for x in range(K - 1, 0, -1):
	v = S[x][0]
	w = -1 * que[0]
	if v < w:
		heappop(que)
		heappush(que, -1 * v)
		uma -= v
		uma += w
	ans = max(ans, uma + x * x)
print(ans)


import heapq
(n, k) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = 0
for i in range(n - 1, n - k - 1, -1):
	(ti, di) = sushi[i]
	if ti in t.keys():
		x.append(di)
		t[ti] += 1
	else:
		t[ti] = 1
	z += di
p = len(t.keys())
ans = z + p ** 2
j = 1
for i in range(n - k - 1, -1, -1):
	if j == len(x) + 1:
		break
	(ti, di) = sushi[i]
	if ti not in t.keys():
		t[ti] = 1
		z += di - x[-j]
		p += 1
		j += 1
		ans = max(ans, z + p ** 2)
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: (x[0], x[1]), reverse=True)
x = []
y = []
y.append(td[0][1])
for i in range(1, N):
	if td[i][0] != td[i - 1][0]:
		y.append(td[i][1])
	else:
		x.append(td[i][1])
x.sort(reverse=True)
y.sort(reverse=True)
ans = 0
sum_y = 0
sum_x = []
tmp = 0
sum_x.append(0)
for i in range(len(x)):
	tmp += x[i]
	sum_x.append(tmp)
for i in range(1, min(K, len(y)) + 1):
	sum_y += y[i - 1]
	if len(sum_x) < K - i + 1:
		continue
	ans = max(ans, sum_y + sum_x[K - i] + i * i)
print(ans)


mi = lambda : map(int, input().split())
(n, k) = mi()
sushis = [list(mi()) for _ in range(n)]
types = set()
sushis.sort(key=lambda x: x[1], reverse=True)
bp = tp = sp = 0
exts = []
for (t, d) in sushis[:k]:
	bp += d
	if t in types:
		exts += (d,)
	else:
		types.add(t)
		tp += 1
sp = bp + tp ** 2
for (t, d) in sushis[k:]:
	if not exts:
		break
	if t not in types:
		types.add(t)
		bp += d - exts.pop()
		tp += 1
		sp = max(sp, bp + tp ** 2)
print(sp)


(N, K) = map(int, input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x: x[1], reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
	ans += td[i][1]
	if not td[i][0] in ls:
		ls.add(td[i][0])
	else:
		dl.append(td[i][1])
ans = ans + len(ls) ** 2
res = ans
for i in range(K, N):
	if not dl:
		break
	if td[i][0] in ls:
		continue
	ans += len(ls) * 2 + 1
	ans += td[i][1]
	ans -= dl[-1]
	del dl[-1]
	res = max(res, ans)
	ls.add(td[i][0])
print(res)


import heapq
from operator import itemgetter
(n, k) = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(n)]
sushi.sort(key=itemgetter(1), reverse=True)
que = []
kind = set()
res = 0
for (t, d) in sushi[:k]:
	if t in kind:
		heapq.heappush(que, d)
	else:
		kind.add(t)
	res += d
res += len(kind) ** 2
val = res
for (t, d) in sushi[k:]:
	if not que:
		break
	if t in kind:
		continue
	val += -heapq.heappop(que) + d + len(kind) * 2 + 1
	kind.add(t)
	res = max(res, val)
print(res)


from collections import Counter
(N, K) = map(int, input().split())
src = [tuple(map(int, input().split())) for i in range(N)]
src.sort(key=lambda x: -x[1])
selected = Counter()
ans = 0
stack = []
for (t, d) in src[:K]:
	ans += d
	selected[t] += 1
	stack.append((t, d))
ans += len(selected) ** 2
tmp = ans
for (t, d) in src[K:]:
	if t in selected:
		continue
	while stack:
		(t0, d0) = stack.pop()
		if selected[t0] > 1:
			tmp += d - d0 + 2 * len(selected) + 1
			ans = max(ans, tmp)
			selected[t0] -= 1
			selected[t] += 1
			break
print(ans)


(n, k) = map(int, input().split())
dt = sorted((tuple(map(int, input().split()))[::-1] for _ in range(n)))[::-1]
r = v = 0
a = []
s = set()
for (i, (d, t)) in enumerate(dt, 1):
	if t in s:
		if i <= k:
			a.append(d)
			v += d
	else:
		if i > k:
			if not a:
				break
			v -= a.pop()
		v += d
		s.add(t)
	r = max(r, len(s) ** 2 + v)
print(r)


import collections
from collections import deque
(n, k) = map(int, input().split())
t = [list(map(int, input().split())) for i in range(n)]
q = deque()
ans = 0
r = [0] * (n + 1)
t.sort(key=lambda x: x[1], reverse=True)
for i in range(k):
	ans += t[i][1]
	if r[t[i][0]] == 0:
		r[t[i][0]] = 1
	else:
		q.append(t[i][1])
v = sum(r)
ans += v ** 2
cnt = ans
for i in range(k, n):
	if r[t[i][0]] == 0 and len(q) != 0:
		r[t[i][0]] = 1
		x = q.pop()
		cnt += t[i][1] + 2 * v + 1 - x
		v += 1
		ans = max(cnt, ans)
print(ans)


import sys

def solve():
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	S = []
	for _ in range(N):
		(t, d) = map(int, input().split())
		S.append((d, t))
	S.sort(reverse=True)
	upperKCount = 0
	appeared = set()
	maxPoint = 0
	for i in range(K):
		maxPoint += S[i][0]
		if S[i][1] not in appeared:
			upperKCount += 1
			appeared |= {S[i][1]}
	maxPoint += upperKCount ** 2
	appeared = set()
	typeMax = []
	typeNum = 0
	typeLower = []
	others = 0
	for (d, t) in S:
		if t in appeared:
			typeLower.append(d)
			others += 1
		else:
			typeMax.append(d)
			typeNum += 1
			appeared |= {t}
	typeMaxSum = [0] * (typeNum + 1)
	typeLowerSum = [0] * (others + 1)
	for i in range(typeNum):
		typeMaxSum[i + 1] = typeMaxSum[i] + typeMax[i]
	for i in range(others):
		typeLowerSum[i + 1] = typeLowerSum[i] + typeLower[i]
	for k in range(upperKCount + 1, min(typeNum, K) + 1):
		maxPoint = max(maxPoint, k ** 2 + typeMaxSum[k] + typeLowerSum[K - k])
	print(maxPoint)
	return 0

def __starting_point():
	solve()
__starting_point()


from heapq import heappop
from heapq import heappush
from heapq import heappushpop
(N, K) = map(int, input().split())
a = [list(map(int, input().split()))[::-1] for i in range(N)]
a.sort(reverse=True)
l = []
dic1 = {}
dic2 = {}
for i in range(K):
	[d, t] = a[i]
	if t in dic1:
		if d > dic2[t]:
			heappush(l, dic2[t])
			dic2[t] = d
		else:
			heappush(l, d)
	else:
		dic1[t] = 1
		dic2[t] = d
s = sum(l) + sum(dic2.values())
x = len(dic1)
ans = s + x ** 2
for i in range(K, N):
	if l == []:
		break
	[d, t] = a[i]
	if not t in dic1:
		dic1[t] = 1
		s += d - heappop(l)
		x += 1
		ans = max(ans, s + x ** 2)
print(ans)


import heapq
(N, K) = list(map(int, input().split()))
I = []
for _ in range(N):
	(t, d) = list(map(int, input().split()))
	I.append((d, t))
I.sort(reverse=True)
h_d = []
h_a = []
wk = 0
kind = 0
ap = set()
for i in range(K):
	(d, t) = I[i]
	wk += d
	if t not in ap:
		ap.add(t)
		kind += 1
	else:
		heapq.heappush(h_d, (d, t))
for i in range(K, N):
	(d, t) = I[i]
	if t not in ap:
		ap.add(t)
		heapq.heappush(h_a, (-1 * d, t))
ans = wk + kind ** 2
while len(h_d) > 0 and len(h_a) > 0:
	(d1, t1) = heapq.heappop(h_d)
	(d2, t2) = heapq.heappop(h_a)
	d2 = -1 * d2
	wk = wk - d1 + d2
	kind += 1
	ans = max(ans, wk + kind ** 2)
print(ans)


from operator import itemgetter
(n, k) = map(int, input().split())
td = [tuple((int(x) for x in input().split())) for _ in range(n)]
a = sorted(td, key=itemgetter(1), reverse=True)
ans = [0]
s = set()
t = []
for i in range(k):
	ans[0] += a[i][1]
	if a[i][0] not in s:
		s.add(a[i][0])
	else:
		t.append(a[i][1])
p = len(s)
q = len(t) - 1
if q < 0:
	print(ans[0] + k * k)
	exit()
v = []
for i in range(k, n):
	if a[i][0] not in s:
		s.add(a[i][0])
		v.append(a[i][1])
ans[0] += p * p
d = 0
for x in v:
	ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
	p += 1
	d += 1
	q -= 1
	if q < 0:
		break
print(max(ans))


import sys
from heapq import heapify, heappop, heappush

def solve():
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	S = [None] * N
	for i in range(N):
		(t, d) = map(int, input().split())
		S[i] = (-d, t)
	heapify(S)
	base_point = 0
	appeared_type = set()
	type_Num = 0
	duplicated = []
	heapify(duplicated)
	for i in range(K):
		(d, t) = heappop(S)
		if t in appeared_type:
			base_point -= d
			heappush(duplicated, -d)
		else:
			base_point -= d
			appeared_type |= {t}
			type_Num += 1
	Ans = base_point + type_Num * type_Num
	while S:
		(d, t) = heappop(S)
		if t in appeared_type:
			continue
		elif not duplicated:
			continue
		else:
			remove = heappop(duplicated)
			base_point -= d + remove
			type_Num += 1
			appeared_type |= {t}
			Ans = max(Ans, base_point + type_Num * type_Num)
	print(Ans)
	return 0

def __starting_point():
	solve()
__starting_point()


(n, k) = list(map(int, input().split()))
td = sorted([list(map(int, input().split())) for i in range(n)], reverse=True, key=lambda x: x[1])
ans = 0
kl = dict()
for i in range(k):
	ans += td[i][1]
	if td[i][0] in kl:
		kl[td[i][0]] += 1
	else:
		kl[td[i][0]] = 1
l = len(kl)
ans += l ** 2
ans_ = ans
now = k - 1
for i in range(k, n):
	if td[i][0] not in kl:
		while now >= 0:
			if kl[td[now][0]] > 1:
				mi = td[now]
				kl[mi[0]] -= 1
				now -= 1
				break
			now -= 1
		if now == -1:
			break
		else:
			ans = ans + 2 * l + 1 - mi[1] + td[i][1]
			kl[td[i][0]] = 1
			ans_ = max(ans, ans_)
			l += 1
print(ans_)


(N, K) = map(int, input().split())
TD = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: -x[1])
q = []
ans = 0
s = set()
for i in range(K):
	ans += TD[i][1]
	if TD[i][0] in s:
		q.append(TD[i][1])
	s.add(TD[i][0])
ans += len(s) ** 2
k1 = K
ans1 = ans
while k1 < N and q:
	if TD[k1][0] not in s:
		ans1 = ans1 + TD[k1][1] - q.pop() - len(s) ** 2 + (len(s) + 1) ** 2
		ans = max(ans, ans1)
		s.add(TD[k1][0])
	k1 += 1
print(ans)


import heapq as hq
(n, k) = map(int, input().split())
A = []
S0 = []
S1 = []
for i in range(n):
	(t, d) = map(int, input().split())
	A.append([t, d])
A = list(reversed(sorted(A)))
now = 0
for i in range(n):
	t = A[i][0]
	d = A[i][1]
	if now == t:
		S0.append(-d)
	else:
		S1.append(-d)
		now = t
hq.heapify(S0)
hq.heapify(S1)
C = []
x = 0
y = 0
for i in range(k):
	if len(S0) == 0:
		x += -hq.heappop(S1)
		y += 1
		continue
	if len(S1) == 0:
		s0 = -hq.heappop(S0)
		x += s0
		hq.heappush(C, s0)
		continue
	if S1[0] <= S0[0]:
		x += -hq.heappop(S1)
		y += 1
	else:
		s0 = -hq.heappop(S0)
		x += s0
		hq.heappush(C, s0)
ans = x + y ** 2
for i in range(min(len(S1), len(C))):
	c = hq.heappop(C)
	s1 = -hq.heappop(S1)
	x += s1 - c
	y += 1
	ans = max(x + y ** 2, ans)
print(ans)


import heapq
(n, k) = map(int, input().split())
z = [0, 1]
for i in range(1, n):
	z.append(z[i] + 2)
s = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])
q = []
v = 0
ans = 0
l = [0] * -~n
for a in s[:k]:
	if not l[a[0]]:
		v += 1
		ans += z[v]
	else:
		heapq.heappush(q, a[1])
	l[a[0]] = 1
	ans += a[1]
tem = ans
for a in s[k:]:
	if not q:
		break
	if l[a[0]]:
		continue
	l[a[0]] = 1
	v += 1
	t = heapq.heappop(q)
	tem = tem - t + a[1] + z[v]
	ans = max(ans, tem)
print(ans)


import heapq
from typing import List

def main():
	(n, k) = list(map(int, input().split()))
	v = []
	for _ in range(n):
		(t, d) = list(map(int, input().split()))
		v.append((t, d))
	print(vs(v, k))

def vs(v: List[List[int]], k: int) -> int:
	v.sort(key=lambda x: x[1], reverse=True)
	h0 = []
	h1 = []
	s = set()
	types = 0
	op = 0
	for i in range(k):
		(t, d) = v[i]
		op += d
		if t in s:
			heapq.heappush(h0, d)
			continue
		types += 1
		s.add(t)
	for i in range(k, len(v)):
		(t, d) = v[i]
		if not t in s:
			s.add(t)
			heapq.heappush(h1, -d)
	result = op + types ** 2
	while len(h0) > 0 and len(h1) > 0:
		d0 = heapq.heappop(h0)
		d1 = -heapq.heappop(h1)
		op = op - d0 + d1
		types += 1
		tmp = op + types ** 2
		if tmp > result:
			result = tmp
	return result

def __starting_point():
	main()
__starting_point()


(N, K) = list(map(int, input().split()))
TDlist = []
for x in range(0, N):
	TDlist.append(list(map(int, input().split())))
TDlist = sorted(TDlist, key=lambda x: x[1], reverse=True)
kinds = set()
seconds = []
answer = 0
for x in TDlist[:K]:
	if not x[0] in kinds:
		kinds.add(x[0])
	else:
		seconds.append(x[1])
	answer += x[1]
answer += len(kinds) ** 2
score = answer
for x in TDlist[K:]:
	if seconds == []:
		break
	if x[0] in kinds:
		continue
	kinds.add(x[0])
	y = seconds.pop()
	score += x[1] - y + (len(kinds) * 2 - 1)
	answer = max(score, answer)
print(answer)


from heapq import *
I = lambda : list(map(int, input().split()))
(n, k) = I()
q = []
v = i = T = A = 0
l = [0] * -~n
for (a, b) in sorted([I() for _ in [0] * n], key=lambda x: -x[1]):
	if i < k:
		if l[a]:
			heappush(q, b)
		else:
			T += v * 2 + 1
			v += 1
		T += b
	elif l[a] ^ 1 and q:
		T += b + v * 2 + 1 - heappop(q)
		v += 1
	A = max(A, T)
	i += 1
	l[a] = 1
print(A)


from operator import itemgetter
(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1), reverse=True)
(t, d) = zip(*td)
s = set()
q = []
tmp = 0
now = 0
for i in range(K):
	if t[i] not in s:
		s.add(t[i])
	else:
		q.append(d[i])
	tmp += d[i]
	now += 1
kind = len(s)
sums = [-100000000000] * (kind + 1)
sums[kind] = tmp
for i in range(K, N):
	if not q:
		break
	if t[i] not in s:
		s.add(t[i])
		tmp = q.pop()
		kind += 1
		sums.append(sums[kind - 1] + d[i] - tmp)
for i in range(len(sums)):
	sums[i] += i ** 2
print(max(sums))


import heapq
from collections import deque
(n, k) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	l[i].reverse()
	l[i][0] *= -1
heapq.heapify(l)
check = [0 for i in range(10 ** 5 + 1)]
L = []
L2 = []
L2 = deque(L2)
ans = []
for i in range(k):
	x = heapq.heappop(l)
	if check[x[1]] == 0:
		L.append(-x[0])
		check[x[1]] = 1
	else:
		L2.append(-x[0])
p = sum(check)
ans.append(sum(L) + sum(L2) + p ** 2)
y = n - k
while y != 0:
	x = heapq.heappop(l)
	if check[x[1]] == 0:
		L.append(-x[0])
		check[x[1]] = 1
		if len(L2) == 0:
			break
		z = L2.pop()
		p += 1
		ans.append(ans[-1] - (p - 1) ** 2 - x[0] - z + p ** 2)
	y -= 1
print(max(ans))


(n, k) = map(int, input().split())
TD = []
for i in range(n):
	(t, d) = map(int, input().split())
	TD.append([t, d])
TD.sort(key=lambda x: x[1], reverse=True)
V = set()
S = []
ans = 0
for (t, d) in TD[:k]:
	ans += d
	if t in V:
		S.append(d)
	else:
		V.add(t)
ans += len(V) ** 2
x = ans
for (t, d) in TD[k:]:
	if S == []:
		break
	if not t in V:
		x = x - S.pop() + d - len(V) ** 2 + (len(V) + 1) ** 2
		V.add(t)
		ans = max(x, ans)
print(ans)


from heapq import heappop, heappush
(n, k) = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst = sorted(lst, reverse=True, key=lambda x: x[1])
q = []
v = set()
cnt = 0
for (t, d) in lst[:k]:
	cnt += d
	if t in v:
		heappush(q, d)
	else:
		v.add(t)
cnt += len(v) ** 2
ans = cnt
for (t, d) in lst[k:]:
	if t not in v and len(q) != 0:
		x = heappop(q)
		cnt += d + 2 * len(v) + 1 - x
		v.add(t)
		ans = max(ans, cnt)
print(ans)


import heapq
(N, K) = map(int, input().split())
que = []
for i in range(N):
	(t, d) = map(int, input().split())
	que.append((t, d))
que.sort(key=lambda x: -x[1])
NOW = que[:K]
N_set = set()
sums = 0
cnt = [0 for i in range(N + 1)]
(ng, ok, sub) = ([], [], [])
heapq.heapify(ng)
heapq.heapify(ok)
heapq.heapify(sub)
for (index, value) in NOW:
	sums += value
	cnt[index] += 1
	heapq.heappush(ng, (value, index))
	N_set.add(index)
while ng:
	(value, index) = heapq.heappop(ng)
	if cnt[index] > 1:
		heapq.heappush(ok, (value, index))
		cnt[index] -= 1
	elif cnt[index] == 1:
		heapq.heappush(sub, (value, index))
ng = sub
S = len(N_set)
ans = S ** 2 + sums
for i in range(K, N):
	(taste, value) = que[i]
	if taste in N_set:
		pass
	elif ok:
		(min_value, m_taste) = heapq.heappop(ok)
		sums -= min_value
		sums += value
		S += 1
		cnt[taste] += 1
		N_set.add(taste)
		cnt[m_taste] -= 1
		heapq.heappush(ng, (value, taste))
		ans = max(ans, S ** 2 + sums)
print(ans)


(N, K) = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
xs = sorted(TD, key=lambda x: -x[1])
baset = 0
ts = set([])
ds = []
for (t, d) in xs[:K]:
	baset += d
	if not t in ts:
		ts.add(t)
	else:
		ds.append(d)
result = baset + len(ts) ** 2
r = result
for (t, d) in xs[K:]:
	if not ds:
		break
	if not t in ts:
		r += 2 * len(ts) + 1
		r += d - ds.pop()
		ts.add(t)
		result = max(result, r)
print(result)


(N, K) = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]
top = [-10 ** 10] * (N + 1)
sub = [0]
cnt = 0
for (t, d) in sushi:
	if top[t] < d:
		sub.append(top[t])
		top[t] = d
	else:
		sub.append(d)
top.sort(reverse=True)
sub.sort(reverse=True)
top_dp = [0] * (N + 1)
sub_dp = [0] * (N + 2)
top_dp[1] = top[0]
sub_dp[1] = sub[0]
for i in range(1, N):
	top_dp[i + 1] = top_dp[i] + top[i]
for i in range(1, len(sub)):
	sub_dp[i + 1] = sub_dp[i] + sub[i]
dp = [0] * (K + 1)
for i in range(1, K + 1):
	dp[i] = top_dp[i] + sub_dp[K - i] + i * i
print(max(dp))


def main():
	from heapq import heappush, heappop
	from operator import itemgetter
	import sys
	input = sys.stdin.readline
	(N, K) = list(map(int, input().split()))
	dd = []
	for _ in range(N):
		(t, d) = list(map(int, input().split()))
		t -= 1
		dd.append((d, t))
	dd.sort(key=itemgetter(0), reverse=True)
	ret = 0
	biggest = [-1] * N
	h = []
	kinds = 0
	for (d, t) in dd[:K]:
		ret += d
		if ~biggest[t]:
			if biggest[t] > d:
				heappush(h, d)
			else:
				heappush(h, biggest[t])
				biggest[t] = d
		else:
			kinds += 1
			ret += kinds * 2 - 1
			biggest[t] = d
	ans = ret
	for (d, t) in dd[K:]:
		if ~biggest[t]:
			continue
		if not h:
			break
		kinds += 1
		diff = d + kinds * 2 - 1 - h[0]
		ret += diff
		if ans < ret:
			ans = ret
		biggest[t] = d
		heappop(h)
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, k) = list(map(int, input().split()))
s = set()
l = []
ln = [[] for i in range(n)]
for i in range(n):
	(t, m) = list(map(int, input().split()))
	l.append([m, t - 1])
	ln[t - 1].append(m)
l.sort(reverse=True)
cand = []
ans = 0
mod = []
for i in range(k):
	ans += l[i][0]
	if l[i][1] in s:
		mod.append(l[i][0])
	else:
		s.add(l[i][1])
x = len(s)
now = ans + x ** 2
for i in range(n):
	if i in s or ln[i] == []:
		continue
	cand.append(max(ln[i]))
cand.sort(reverse=True)
for i in range(min(len(mod), len(cand))):
	ans += cand[i] - mod[-1 - i]
	x += 1
	now = max(now, ans + x ** 2)
print(now)


(N, K) = map(int, input().split())
X = []
for i in range(N):
	(t, d) = map(int, input().split())
	X.append((d, t))
X.sort(reverse=True)
(p, v) = (0, set([]))
pp = []
for i in range(K):
	p += X[i][0]
	if X[i][1] not in v:
		v.add(X[i][1])
	else:
		pp.append((X[i][0], X[i][1]))
Ans = p + len(v) ** 2
ans = Ans
for i in range(K, N):
	if X[i][1] not in v and len(pp) > 0:
		temp = pp[-1]
		pp = pp[:len(pp) - 1]
		ans = ans - temp[0] + X[i][0] - len(v) ** 2 + (len(v) + 1) ** 2
		v.add(X[i][1])
		Ans = max(Ans, ans)
print(Ans)


import sys
input = sys.stdin.readline
from collections import defaultdict
(N, K) = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]
data.sort(key=lambda x: -x[1])
KISO = 0
EAT = defaultdict(int)
for i in range(K):
	(t, v) = data[i]
	EAT[t] += 1
	KISO += v
SHURUI = len(EAT)
l = K - 1
r = K
MAX = KISO + SHURUI ** 2
while True:
	if l < 0 or r >= N:
		break
	(a, b) = data[l]
	(c, d) = data[r]
	if EAT[a] == 1:
		l -= 1
		continue
	if EAT[c] != 0:
		r += 1
		continue
	EAT[a] -= 1
	EAT[c] += 1
	KISO -= b
	KISO += d
	SHURUI += 1
	l -= 1
	r += 1
	MAX = max(MAX, KISO + SHURUI ** 2)
print(MAX)


from heapq import heappush, heappop
(n, k) = map(int, input().split())
L = []
for i in range(n):
	(t, d) = map(int, input().split())
	heappush(L, (-d, t))
LL = []
sum = 0
s = set()
for i in range(k):
	(d, t) = heappop(L)
	if t in s:
		heappush(LL, (-d, t))
	s.add(t)
	sum += -d
ans = len(s) ** 2 + sum
while L and LL:
	(d, t) = heappop(L)
	if t not in s:
		s.add(t)
		(dd, _) = heappop(LL)
		sum = sum - dd + -d
		ans = max(ans, len(s) ** 2 + sum)
print(ans)


from collections import deque
(n, k) = list(map(int, input().split()))
td = [list(map(int, input().split())) for i in range(n)]
td = sorted(td, key=lambda x: x[1], reverse=True)
set_ = set()
val = 0
duplicated = deque([])
for (t_tmp, d_tmp) in td[:k]:
	val += d_tmp
	if t_tmp in set_:
		duplicated.append(d_tmp)
	else:
		set_.add(t_tmp)
now = val + len(set_) ** 2
nx = deque(td[k:])
ans = now
c = len(set_)
while len(set_) < k and nx:
	(i, j) = nx.popleft()
	if i in set_:
		continue
	d = duplicated.pop()
	diff = j - d + 2 * c + 1
	set_.add(i)
	ans = max(ans, now + diff)
	now += diff
	c += 1
print(ans)


(N, K) = map(int, input().split())
l = []
m = []
s = set()
for i in range(N):
	(t, d) = map(int, input().split())
	l.append((d, t))
l.sort(reverse=True)
ans = K ** 2
t = 0
i = 0
j = 0
for _ in range(K):
	while i < N and l[i][1] in s:
		m.append(l[i])
		i += 1
	if i < N and (m and j < len(m)) and (l[i][0] >= m[j][0] - (2 * K - 1 - 2 * t)) or (not m or j >= len(m)):
		ans += l[i][0]
		s.add(l[i][1])
		i += 1
	else:
		ans += m[j][0] - (2 * K - 1 - 2 * t)
		j += 1
		t += 1
print(ans)


import heapq
(N, K) = list(map(int, input().split()))
td = []
td_ = []
group = set()
total = 0
for i in range(N):
	(t, d) = list(map(int, input().split()))
	heapq.heappush(td, (-d, t))
for i in range(K):
	(d, t) = heapq.heappop(td)
	total -= d
	if t not in group:
		group.add(t)
	else:
		heapq.heappush(td_, -d)
length = len(group)
ans = length ** 2 + total
while td and td_:
	(d, t) = heapq.heappop(td)
	if t not in group:
		group.add(t)
		d_ = heapq.heappop(td_)
		total = total - d_ - d
		length += 1
		ans = max(ans, length ** 2 + total)
print(ans)


(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for i in range(n)]
td = sorted(td, key=lambda x: x[1], reverse=True)
sushi = [[] for i in range(2)]
used = set()
for (t, d) in td:
	if t in used:
		sushi[0].append(d)
	else:
		sushi[1].append(d)
		used.add(t)
y = k - min(k, len(sushi[0]))
sushi = list(reversed(sushi[0][:k])) + sushi[1][:k]
sum = sum(sushi[:k])
ans = sum + y ** 2
for i in range(len(sushi) - k):
	sum += sushi[k + i] - sushi[i]
	ans = max(ans, sum + (y + i + 1) ** 2)
print(ans)


(N, K) = map(int, input().split())
TD = [[int(j) for j in input().split()] for i in range(N)]
TD = sorted(TD, key=lambda x: -x[1])
point = 0
stack = []
kind = set()
for (t, d) in TD[:K]:
	point += d
	if t in kind:
		stack.append(d)
	else:
		kind.add(t)
point += len(kind) ** 2
ans = point
for (t, d) in TD[K:]:
	if not stack:
		break
	if not t in kind:
		point += d - stack.pop() + 2 * len(kind) + 1
		kind.add(t)
		ans = max(ans, point)
print(ans)


(n, k) = [int(item) for item in input().split()]
sushi = [[int(item) for item in input().split()] for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
kind = set()
changeable = []
points = 0
for i in range(k):
	points += sushi[i][1]
	if sushi[i][0] in kind:
		changeable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])
points += len(kind) ** 2
ans = points
for i in range(k, n):
	if not changeable:
		break
	if sushi[i][0] not in kind:
		kind.add(sushi[i][0])
		points += sushi[i][1] - (len(kind) - 1) ** 2 + len(kind) ** 2 - changeable.pop()
		ans = max(ans, points)
print(ans)


from heapq import heappop, heappush
(N, K) = map(int, input().split())
td = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = set()
count = 0
for (t, d) in td[:K]:
	count += d
	if t in v:
		heappush(q, d)
	else:
		v.add(t)
count += len(v) ** 2
ans = count
for (t, d) in td[K:]:
	if t not in v and len(q) != 0:
		x = heappop(q)
		count += d + 2 * len(v) + 1 - x
		v.add(t)
		ans = max(ans, count)
print(ans)


(N, K) = map(int, input().split())
inf = 10 ** 18
sushi = [[-inf] for _ in range(N)]
for i in range(N):
	(t, d) = map(int, input().split())
	sushi[t - 1].append(d)
for i in range(N):
	sushi[i].sort(reverse=True)
sushi.sort(key=lambda x: x[0], reverse=True)
que = []
res = 0
for i in range(K):
	res += sushi[i][0]
	for j in sushi[i][1:]:
		que.append(j)
que.sort()
cur = res
res += K ** 2
for var in range(1, K)[::-1]:
	a = que.pop()
	b = sushi[var][0]
	cur += a - b
	res = max(res, cur + var ** 2)
print(res)


from heapq import heappush, heappop
(N, K) = map(int, input().split(' '))
h = []
for _ in range(N):
	(t, d) = map(int, input().split(' '))
	heappush(h, (-d, t))
dsum = 0
used = {}
q = []
for _ in range(K):
	(d, t) = heappop(h)
	if t not in used:
		used[t] = 1
	else:
		heappush(q, (-d, t))
	dsum += -d
res = len(used) ** 2 + dsum
while h and q:
	(d, t) = heappop(h)
	if t not in used:
		used[t] = 1
		(m, _) = heappop(q)
		dsum = dsum - m - d
		res = max(res, len(used) ** 2 + dsum)
print(res)


from collections import Counter
(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for i in range(n)]
td.sort(key=lambda x: x[1], reverse=True)
ans = list(range(k))
ansv = sum((td[i][1] for i in range(k)))
c = Counter((td[i][0] for i in range(k)))
cnt = len(c)
ansv += len(c) ** 2
ptr = k
ansls = [ansv]
for i in range(k - 1, -1, -1):
	(t, d) = td[ans[i]]
	if ptr < n and c[t] > 1:
		while ptr < n and c[td[ptr][0]] >= 1:
			ptr += 1
		if ptr >= n:
			break
		ansv = ansv - d + 2 * cnt + 1 + td[ptr][1]
		c[t] -= 1
		c[td[ptr][0]] += 1
		cnt += 1
		ptr += 1
		ansls.append(ansv)
print(max(ansls))


import heapq
(N, K) = map(int, input().split())
TD = [list(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda x: x[1], reverse=True)
NETA = set()
duplication = []
heapq.heapify(duplication)
ans = 0
for (t, d) in TD[:K]:
	if t in NETA:
		heapq.heappush(duplication, d)
	else:
		NETA.add(t)
	ans += d
s = [-float('inf')] * (K + 1)
cnt = len(NETA)
s[cnt] = ans
for (t, d) in TD[K:]:
	if t in NETA:
		continue
	elif duplication:
		x = heapq.heappop(duplication)
		ans += d - x
		NETA.add(t)
		cnt += 1
		s[cnt] = ans
for i in range(K + 1):
	s[i] += i * i
print(max(s))


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
sushi = [None] * N
for i in range(N):
	(t, d) = map(int, input().split())
	sushi[i] = (d, t - 1)
sushi.sort(reverse=True)
types = set()
cand = []
s = x = 0
for (d, t) in sushi[:K]:
	if t in types:
		heappush(cand, d)
	else:
		types.add(t)
		x += 1
	s += d
ans = s + x * x
for (d, t) in sushi[K:]:
	if t in types:
		continue
	if not cand:
		break
	dr = heappop(cand)
	s += d - dr
	types.add(t)
	x += 1
	ans = max(ans, s + x * x)
print(ans)


(N, K) = map(int, input().split())
TD = [list(map(int, input().split())) for _ in [0] * N]
TD.sort(key=lambda x: (-x[1], x[0]))
use = TD[:K]
var = set()
lock = []
unlock = []
for (t, d) in use:
	if t in var:
		unlock.append(d)
	else:
		var.add(t)
		lock.append(d)
unlock.sort(reverse=True)
Dscore = sum(lock) + sum(unlock)
v = len(var)
Vscore = v * v
ans = Dscore + Vscore
unused = TD[K:][::-1]
while unlock and unused:
	(t, d) = unused.pop()
	if t in var:
		continue
	trash = unlock.pop()
	var.add(t)
	lock.append(d)
	v += 1
	Dscore += d - trash
	Vscore = v * v
	ans = max(ans, Dscore + Vscore)
print(ans)


(n, k) = map(int, input().split())
td = [tuple(map(int, input().split())) for _ in range(n)]
td.sort(key=lambda x: x[1])
kind = set()
base = 0
rest = []
for i in range(k):
	(t, d) = td.pop()
	base += d
	if t in kind:
		rest.append(d)
	kind.add(t)
cntk = len(kind)
ans = base + cntk * cntk
while len(rest) > 0:
	bd = rest.pop()
	while len(td) > 0:
		(nt, nd) = td.pop()
		if nt not in kind:
			break
	else:
		break
	base += nd - bd
	cntk += 1
	ans = max(ans, base + cntk * cntk)
	kind.add(nt)
print(ans)


(N, K) = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
TD_sorted = sorted(TD, key=lambda x: -x[1])
d_sum = 0
t_set = set([])
d_surplus = []
for (t, d) in TD_sorted[:K]:
	d_sum += d
	if not t in t_set:
		t_set.add(t)
	else:
		d_surplus.append(d)
a = d_sum + len(t_set) ** 2
answer = a
for (t, d) in TD_sorted[K:]:
	if not d_surplus:
		break
	if not t in t_set:
		a += 2 * len(t_set) + 1
		a += d
		a -= d_surplus.pop()
		t_set.add(t)
		answer = max(answer, a)
print(answer)


import heapq
from operator import itemgetter
(n, k) = map(int, input().split())
td = sorted([list(map(int, input().split())) for i in range(n)], key=itemgetter(1), reverse=True)
neta = [0] * (n + 1)
hq = []
kind = 0
ans = 0
for (t, d) in td[:k]:
	if neta[t]:
		hq.append(d)
	else:
		kind += 1
	neta[t] += 1
	ans += d
ans += kind ** 2
heapq.heapify(hq)
now = k
new_ans = ans
while hq and now < n:
	(t, d) = (td[now][0], td[now][1])
	if not neta[t]:
		MIN = heapq.heappop(hq)
		new_ans += d - MIN + 2 * kind + 1
		ans = max(ans, new_ans)
		kind += 1
		neta[t] += 1
	now += 1
print(ans)


import heapq
(n, k) = map(int, input().split())
td = [[0] * 2 for _ in range(n)]
for i in range(n):
	(t, d) = map(int, input().split())
	(td[i][0], td[i][1]) = (d, t)
td.sort(reverse=True)
di = set()
sa = []
heapq.heapify(sa)
ans = 0
for (d, t) in td[:k]:
	if t in di:
		heapq.heappush(sa, d)
	else:
		di.add(t)
	ans += d
s = [-10 ** 18] * (k + 1)
cnt = len(di)
s[cnt] = ans
for (d, t) in td[k:]:
	if t in di:
		continue
	elif sa:
		x = heapq.heappop(sa)
		ans += d - x
		di.add(t)
		cnt += 1
		s[cnt] = ans
for i in range(k + 1):
	s[i] += i * i
print(max(s))


(N, K) = map(int, input().split())
TD = [[int(x) for x in input().split()] for _ in range(N)]
TD.sort(key=lambda x: x[1], reverse=True)
T = 0
neta = set()
doublecounts = []
ans = []
for i in range(K):
	T += TD[i][1]
	if not TD[i][0] in neta:
		neta.add(TD[i][0])
	else:
		doublecounts.append(TD[i][1])
ans.append(T + len(neta) ** 2)
for i in range(K, N):
	if len(doublecounts) == 0:
		break
	if not TD[i][0] in neta:
		T -= doublecounts.pop(-1)
		T += TD[i][1]
		neta.add(TD[i][0])
		ans.append(T + len(neta) ** 2)
print(max(ans))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
SUSHI = []
for _ in range(n):
	(t, d) = map(int, input().split())
	SUSHI.append((d, t))
SUSHI.sort(reverse=True)
NEW = {i: True for i in range(1, n + 1)}
(x, y) = (0, 0)
(A, B) = ([], [])
for (d, t) in SUSHI[:k]:
	if NEW[t]:
		x += d
		y += 1
		NEW[t] = False
	else:
		x += d
		A.append(d)
for (d, t) in SUSHI[k:]:
	if NEW[t]:
		B.append(d)
		NEW[t] = False
B.sort()
answer = x + y ** 2
while A and B:
	(a, b) = (A.pop(), B.pop())
	x -= a
	x += b
	y += 1
	if x + y ** 2 > answer:
		answer = x + y ** 2
print(answer)


(n, k) = map(int, input().split())
sushi = [[int(i) for i in input().split()] for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
eaten = [False] * n
d1 = [0]
d2 = [0]
for i in range(n):
	(t, d) = sushi[i]
	t -= 1
	if eaten[t]:
		d1.append(d1[-1] + d)
	else:
		eaten[t] = True
		d2.append(d2[-1] + d)
ans = 0
for i in range(1, k + 1):
	if k - i >= len(d1):
		continue
	if i >= len(d2):
		continue
	ans = max(ans, d1[k - i] + d2[i] + i * i)
print(ans)


import heapq
(N, K) = list(map(int, input().split()))
L = [[] for _ in range(N)]
All = []
s = set([])
for i in range(N):
	(t, d) = list(map(int, input().split()))
	t -= 1
	heapq.heappush(L[t], -d)
	heapq.heappush(All, [-d, t])
	s.add(t)
point = 0
ns = 0
later = []
now = []
syurui = set([])
while len(now) < K and All:
	temp = heapq.heappop(All)
	if temp[1] not in syurui:
		ns += 1
		point -= temp[0]
		syurui.add(temp[1])
		heapq.heappush(now, -1 * temp[0])
	else:
		later.append(temp)
for i in later:
	heapq.heappush(All, i)
point += ns * ns
while len(now) < K:
	temp = heapq.heappop(All)
	point -= temp[0]
	heapq.heappush(now, -1 * temp[0])
while All and now[0] < -1 * All[0][0]:
	temp = heapq.heappop(All)
	dele = heapq.heappop(now)
	upoint = point - temp[0] - dele - ns * ns + (ns - 1) ** 2
	if upoint >= point:
		point = upoint
		ns -= 1
	else:
		break
print(point)


from collections import *
(n, k) = map(int, input().split())
(d, t) = zip(*sorted((tuple(map(int, input().split()))[::-1] for _ in range(n)))[::-1])
c = Counter(t[:k])
x = len(c)
a = [sum(d[:k])]
for i in range(k)[::-1]:
	if c[t[i]] > 1:
		c[t[i]] -= 1
		a.append(a[-1] - d[i])
b = [0]
for i in range(k, n):
	if c[t[i]] <= 0:
		c[t[i]] += 1
		b.append(b[-1] + d[i])
r = 0
for (i, (v, w)) in enumerate(zip(a, b)):
	r = max(r, v + w + (x + i) ** 2)
print(r)


(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: -x[1])
q = []
v = set()
sd = 0
for (t, d) in td[:K]:
	sd += d
	if t in v:
		q.append(d)
	v.add(t)
ans = len(v) ** 2 + sd
for (t, d) in td[K:]:
	if 0 >= len(q):
		break
	if t in v:
		continue
	v.add(t)
	md = q.pop()
	sd = sd - md + d
	tans = len(v) ** 2 + sd
	ans = max(ans, tans)
print(ans)


from heapq import heappop, heappush
(n, k) = map(int, input().split())
s = []
h = set()
l = [0] * n
for _ in range(n):
	(t, d) = map(int, input().split())
	s.append((d, t - 1))
s = sorted(s, reverse=True)
a = []
num = 0
for i in range(k):
	(d, t) = s[i]
	l[t] += 1
	h.add(t)
	num += d
	if l[t] > 1:
		heappush(a, (d, t))
ans = len(h) ** 2 + num
for j in range(k, n):
	(d, t) = s[j]
	l[t] += 1
	if l[t] >= 2:
		continue
	if len(a) == 0:
		break
	(d1, t1) = heappop(a)
	h.add(t)
	num = num - d1 + d
	ans = max(ans, len(h) ** 2 + num)
print(ans)


import heapq as hq
from collections import Counter
(N, K) = map(int, input().split())
t_d = []
for _ in range(N):
	(t, d) = map(int, input().split())
	t_d.append([t, d])
t_d = sorted(t_d, key=lambda x: -x[1])
kiso = 0
neta = Counter()
stack = []
for (t, d) in t_d[:K]:
	kiso += d
	neta[t] += 1
	hq.heappush(stack, [d, t])
ans = kiso + len(neta) ** 2
for (t, d) in t_d[K:]:
	if neta[t] > 0:
		continue
	while stack:
		(d0, t0) = hq.heappop(stack)
		if neta[t0] > 1:
			kiso += d - d0
			neta[t0] -= 1
			neta[t] += 1
			ans = max(ans, kiso + len(neta) ** 2)
			break
print(ans)


import heapq
(N, K) = map(int, input().split())
L1 = []
L2 = []
S = set()
val = 0
for _ in range(N):
	(t, d) = map(int, input().split())
	L1.append((d, t))
L1.sort(reverse=True)
for i in range(K):
	val += L1[i][0]
	if L1[i][1] in S:
		heapq.heappush(L2, L1[i][0])
	else:
		S.add(L1[i][1])
ans = val + len(S) ** 2
for i in range(K, N):
	if len(L2) == 0:
		break
	if not L1[i][1] in S:
		S.add(L1[i][1])
		val -= heapq.heappop(L2)
		val += L1[i][0]
		ans = max(ans, val + len(S) ** 2)
print(ans)


from heapq import heappush, heappop
(n, k) = map(int, input().split())
kind_value = [[] for _ in range(n + 1)]
for i in range(n):
	(t, d) = map(int, input().split())
	kind_value[t].append(d)
for li in kind_value:
	li.sort()
first_type = [(li[-1], i) for (i, li) in enumerate(kind_value) if li]
first_type.sort(reverse=True)
kind = 0
value_type1 = 0
second_type = []
second_type_sum = 0
second_type_cnt = 0
answer = 0
for (v, i) in first_type:
	kind += 1
	if kind > k:
		break
	value_type1 += v
	for d in kind_value[i][:-1]:
		heappush(second_type, d)
		second_type_sum += d
		second_type_cnt += 1
	while second_type_cnt > k - kind:
		d = heappop(second_type)
		second_type_cnt -= 1
		second_type_sum -= d
	value = kind * kind + value_type1 + second_type_sum
	if answer < value:
		answer = value
print(answer)


(n, k) = [int(x) for x in input().split()]
A = []
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	A.append([b, a, True])
A.sort(reverse=True)
typ = set()
for i in range(n):
	if A[i][1] in typ:
		A[i][2] = False
	else:
		typ.add(A[i][1])
num = 0
for j in range(k):
	if A[j][2] == True:
		num += 1
ans = 0
for i in range(k):
	ans += A[i][0]
ans += num ** 2
curr = ans
nxt = k
lst = k - 1
while True:
	while nxt < n and A[nxt][2] == False:
		nxt += 1
	while lst >= 0 and A[lst][2] == True:
		lst -= 1
	if not (nxt < n and lst >= 0):
		break
	curr += A[nxt][0] - A[lst][0]
	curr += (num + 1) ** 2 - num ** 2
	num += 1
	nxt += 1
	lst -= 1
	ans = max(ans, curr)
print(ans)


import collections
(N, K) = list(map(int, input().split()))
dic = {}
A = []
for _ in range(N):
	(t, d) = list(map(int, input().split()))
	A.append([t, d])
A.sort(key=lambda x: x[1], reverse=True)
val = 0
set_ = set()
duplicated = collections.deque([])
for (t, d) in A[:K]:
	val += d
	if t in set_:
		duplicated.append(d)
	else:
		set_.add(t)
now = val + len(set_) ** 2
nx = collections.deque(A[K:])
ans = now
c = len(set_)
while len(set_) < K and nx:
	(i, j) = nx.popleft()
	if i in set_:
		continue
	d = duplicated.pop()
	diff = j - d + 2 * c + 1
	set_.add(i)
	now += diff
	ans = max(ans, now)
	c += 1
print(ans)


(n, k) = map(int, input().split())
top = [0] * n
sub = []
for _ in range(n):
	(t, d) = map(int, input().split())
	t -= 1
	if top[t] == 0:
		top[t] = d
	elif d > top[t]:
		sub.append(top[t])
		top[t] = d
	else:
		sub.append(d)
top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]
for i in top:
	if i == 0:
		top_sum.append(-1)
	else:
		top_sum.append(top_sum[-1] + i)
for i in sub:
	sub_sum.append(sub_sum[-1] + i)
ans = 0
for i in range(1, k + 1):
	if i + len(sub_sum) - 1 >= k and top_sum[i] != -1:
		ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)
print(ans)


def main():
	(N, K) = list(map(int, input().split()))
	sushi_list = list()
	for _ in range(N):
		(t, d) = list(map(int, input().split()))
		t -= 1
		sushi_list.append((t, d))
	sushi_list.sort(key=lambda s: s[1], reverse=True)
	neta_flag_list = [0] * N
	topk_extra_sushi_list = list()
	additional_sushi_list = list()
	point_topk = 0
	for (k, sushi) in enumerate(sushi_list):
		if k < K:
			if neta_flag_list[sushi[0]] == 1:
				topk_extra_sushi_list.append(sushi)
			point_topk += sushi[1]
		elif neta_flag_list[sushi[0]] == 0:
			additional_sushi_list.append(sushi)
		neta_flag_list[sushi[0]] = 1
	n_neta = K - len(topk_extra_sushi_list)
	point_topk += n_neta ** 2
	(d_extra, d_additional) = (0, 0)
	ans = point_topk
	n_additional_neta = min(K - n_neta, len(topk_extra_sushi_list), len(additional_sushi_list))
	for t in range(1, n_additional_neta + 1):
		n_cur_neta = n_neta + t
		d_extra += topk_extra_sushi_list[-t][1]
		d_additional += additional_sushi_list[t - 1][1]
		point = point_topk - d_extra + d_additional + (n_cur_neta ** 2 - n_neta ** 2)
		ans = max(ans, point)
	print(ans)

def __starting_point():
	main()
__starting_point()


from operator import itemgetter
(N, K) = map(int, input().split())
TD = [list(map(int, input().split())) for _ in range(N)]
TD.sort(key=itemgetter(1), reverse=True)
selected = TD[:K]
dlc = sum(map(itemgetter(1), selected))
variety = set(map(itemgetter(0), selected))
used = set()
overlap = []
for (t, d) in TD[:K]:
	if t not in used:
		used.add(t)
	else:
		overlap.append(d)
answer = dlc + len(variety) ** 2
for (t, d) in TD[K:]:
	if not overlap:
		break
	if t in used:
		continue
	ov = overlap.pop()
	dlc = dlc - ov + d
	used.add(t)
	answer = max(answer, dlc + len(used) ** 2)
print(answer)


(N, K) = list(map(int, input().split()))
S = [tuple(map(int, input().split())) for _ in range(N)]
S.sort(key=lambda x: -x[1])
st = set()
(first_acc, other_acc) = ([0], [0])
for (t, d) in S:
	if t in st:
		other_acc.append(other_acc[-1] + d)
	else:
		st.add(t)
		first_acc.append(first_acc[-1] + d)
ans = 0
for i in range(K + 1):
	if len(first_acc) <= i or len(other_acc) <= K - i:
		continue
	ans = max(ans, first_acc[i] + other_acc[K - i] + i * i)
print(ans)


from heapq import heapify, heappush, heappop
(N, K) = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]
S.sort(key=lambda x: -x[1])
types = set()
RS = []
AS = []
d_sum = 0
for i in range(K):
	(_type, value) = (S[i][0], S[i][1])
	if _type in types:
		heappush(RS, (value, _type))
	else:
		types.add(_type)
	d_sum += value
t_sum = len(types)
d_sum += pow(t_sum, 2)
for i in range(K, N):
	(_type, value) = (S[i][0], S[i][1])
	if not _type in types:
		heappush(AS, (-value, _type))
		types.add(_type)
ans = d_sum
while len(AS) > 0 and len(RS) > 0:
	(av, at) = heappop(AS)
	(rv, rt) = heappop(RS)
	t_sum += 1
	d_sum += -av - rv + pow(t_sum, 2) - pow(t_sum - 1, 2)
	ans = max(ans, d_sum)
print(ans)


(N, K) = map(int, input().split())
sushi = []
for i in range(N):
	(t, d) = map(int, input().split())
	sushi.append((t, d))
sushi.sort(key=lambda x: (x[0], -x[1]))
X = [sushi[0][1]]
Y = []
for i in range(1, N):
	if sushi[i - 1][0] == sushi[i][0]:
		Y.append(sushi[i][1])
	else:
		X.append(sushi[i][1])
X.sort(reverse=True)
Y.sort(reverse=True)
SX = [0]
SY = [0]
for i in X:
	SX.append(SX[-1] + i)
for i in Y:
	SY.append(SY[-1] + i)
ans = 0
for x in range(max(1, K - len(Y)), min(len(SX), K + 1)):
	ans = max(SX[x] + SY[K - x] + x * x, ans)
print(ans)


(N, K) = map(int, input().split())
sushi = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)
typ = set()
ans = 0
cur = 0
rem = []
for (t, d) in sushi:
	if t in typ:
		if K > 0:
			K -= 1
			cur += d
			rem.append(d)
	else:
		typ.add(t)
		cur += d
		if K > 0:
			K -= 1
		elif len(rem):
			cur -= rem.pop()
		else:
			break
	ans = max(ans, cur + len(typ) ** 2)
print(ans)


(N, K) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
typ = set()
lstA = []
lstB = []
for item in sushi:
	if item[0] in typ:
		item[0] = 0
		lstB.append(item[1])
	else:
		typ.add(item[0])
		item[0] = 1
		lstA.append(item[1])
ans = 0
neta = 0
for i in range(K):
	ans += sushi[i][1]
	if sushi[i][0] == 1:
		neta += 1
ans += neta ** 2
C = sum(lstA[:neta])
D = sum(lstB[:K - neta])
for i in range(neta + 1, min(K, len(lstA)) + 1):
	C += lstA[i - 1]
	D -= lstB[K - i]
	tmp = C + D + i ** 2
	ans = max(ans, tmp)
print(ans)


import sys

def input():
	return sys.stdin.readline()[:-1]

def N():
	return int(input())

def NM():
	return map(int, input().split())

def L():
	return list(NM())

def LN(n):
	return [N() for i in range(n)]

def LL(n):
	return [L() for i in range(n)]
(n, k) = NM()
l = LL(n)
l.sort(key=lambda x: -x[1])
from heapq import heappush, heappop, heapify
s = set()
q = []
oisisa = 0
syu = 0
for (t, d) in l[:k]:
	if t in s:
		heappush(q, d)
	else:
		s.add(t)
		syu += 1
	oisisa += d
ans = oisisa + syu ** 2
for (t, d) in l[k:]:
	if q and (not t in s):
		syu += 1
		oisisa += d - heappop(q)
		s.add(t)
	ans = max(ans, oisisa + syu ** 2)
print(ans)


(N, K) = map(int, input().split())
td = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = set()
cnt = 0
for (t, d) in td[:K]:
	cnt += d
	if t in v:
		q.append(d)
	else:
		v.add(t)
cnt += len(v) ** 2
ans = cnt
for (t, d) in td[K:]:
	if t not in v and len(q) != 0:
		x = q.pop()
		cnt += d + 2 * len(v) + 1 - x
		v.add(t)
		ans = max(ans, cnt)
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
from collections import Counter
sel = Counter()
ans = 0
sta = []
for (t, d) in sushi[:k]:
	ans += d
	sel[t] += 1
	sta.append([t, d])
ans += len(sel) ** 2
tmp = ans
for (t, d) in sushi[k:]:
	if t in sel:
		continue
	while sta:
		(tt, dd) = sta.pop()
		if sel[tt] > 1:
			tmp += d - dd + 2 * len(sel) + 1
			ans = max(ans, tmp)
			sel[tt] -= 1
			sel[t] += 1
			break
print(ans)


import itertools
(N, K) = map(int, input().split())
td = {}
for i in range(N):
	(a, b) = map(int, input().split())
	td.setdefault(a, [])
	td[a].append(b)
top = []
rest = []
for k in td.keys():
	td[k].sort()
	top.append(td[k][-1])
	rest += td[k][:-1]
top.sort()
rest.sort()
cumtop = list(itertools.accumulate(reversed(top)))
cumrest = list(itertools.accumulate(reversed(rest)))
ret = 0
for i in range(min(len(top), K)):
	tmp = (i + 1) * (i + 1)
	tmp += cumtop[i]
	if i == K - 1:
		pass
	else:
		if K - i - 2 < 0 or K - i - 2 > len(cumrest) - 1:
			continue
		tmp += cumrest[K - i - 2]
	ret = max(tmp, ret)
print(ret)


from heapq import heappush, heappop
(N, K, *td) = list(map(int, open(0).read().split()))
sushis = [(d, t) for (t, d) in zip(*[iter(td)] * 2)]
sushis.sort(reverse=True)
pq = []
cnt = [0] * (N + 1)
(base, x) = (0, 0)
for (d, t) in sushis[:K]:
	base += d
	if cnt[t] > 0:
		heappush(pq, (d, t))
	elif cnt[t] == 0:
		x += 1
	cnt[t] += 1
ans = base + x * x
for (d, t) in sushis[K:]:
	if not pq:
		break
	if cnt[t] > 0:
		continue
	(_d, _t) = heappop(pq)
	cnt[_t] -= 1
	cnt[t] += 1
	x += 1
	base += d - _d
	ans = max(ans, base + x * x)
print(ans)


(N, K) = map(int, input().split())
dts = []
for _ in range(N):
	(t, d) = map(int, input().split())
	dts.append((d, t - 1))
dts.sort(reverse=True)
tops = []
rests = []
isFounds = [False] * N
for (d, t) in dts:
	if isFounds[t]:
		rests.append(d)
	else:
		tops.append(d)
		isFounds[t] = True
tops.sort(reverse=True)
rests.sort(reverse=True)
xFr = max(1, K - len(rests))
xTo = min(K, len(tops))
iTop = xFr
iRest = K - xFr
sumD = sum(tops[:iTop]) + sum(rests[:iRest])
ans = sumD + xFr ** 2
for x in range(xFr + 1, xTo + 1):
	iRest -= 1
	sumD += tops[iTop] - rests[iRest]
	score = sumD + x ** 2
	ans = max(ans, score)
	iTop += 1
print(ans)


(n, k) = map(int, input().split())
td = list(sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda td: -td[1]))
td2 = []
eaten = set()
dup = 0
score = k * k
i = 0
j = 0
while len(eaten) + dup < k:
	if i < n and td[i][0] in eaten:
		td2.append(td[i])
		i += 1
	else:
		diff = (k - dup) * (k - dup) - (k - dup - 1) * (k - dup - 1)
		if i < n and (j >= len(td2) or td[i][1] >= td2[j][1] - diff):
			(t, d) = td[i]
			score += d
			eaten.add(t)
			i += 1
		else:
			(t, d) = td2[j]
			score += d - diff
			dup += 1
			j += 1
print(score)


(n, k) = map(int, input().split())
a = sorted([list(map(int, input().split())) for i in range(n)], key=lambda x: -x[1])
t = [0] * (n + 1)
(p, q) = (0, 0)
for i in a[:k]:
	p += i[1]
	if t[i[0]] == 0:
		q += 1
	t[i[0]] += 1
s = 0
d = p + q * q
c = a[:k][::-1]
for i in a[k:]:
	if t[i[0]] == 0:
		while s != k:
			if t[c[s][0]] == 1:
				s += 1
			else:
				break
		if s == k:
			break
		else:
			t[i[0]] += 1
			p -= c[s][1] - i[1]
			q += 1
			d = max(d, p + q * q)
			s += 1
print(d)


from collections import defaultdict
(N, K) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
types = set()
max_vals = [0]
other_vals = [0]
for (typ, val) in sushi:
	if typ not in types:
		max_vals.append(max_vals[-1] + val)
		types.add(typ)
	else:
		other_vals.append(other_vals[-1] + val)
max_score = 0
for k in range(1, K + 1):
	if K - k < len(other_vals) and k < len(max_vals):
		score = max_vals[k] + other_vals[K - k] + k ** 2
		max_score = max(max_score, score)
print(max_score)


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, K) = lr()
TD = [lr() for _ in range(N)]
heap = []
kind = 0
happy = 0
used = set()
TD.sort(key=lambda x: x[1], reverse=True)
for (t, d) in TD[:K]:
	if t not in used:
		used.add(t)
		kind += 1
	else:
		heappush(heap, d)
	happy += d
cand = [happy + kind ** 2]
for (t, d) in TD[K:]:
	if not heap:
		break
	if t in used:
		continue
	h = heappop(heap)
	happy += d - h
	kind += 1
	used.add(t)
	cand.append(happy + kind ** 2)
answer = max(cand)
print(answer)


import sys
import math
ni = lambda : int(ns())
na = lambda : list(map(int, input().split()))
ns = lambda : input()
(N, K) = na()
S = [na() for i in range(N)]
S.sort(key=lambda x: x[1], reverse=True)
res = []
tmp = 0
d = set([])
ds = []
for (t, dd) in S[:K]:
	tmp += dd
	if t in d:
		ds.append(dd)
	else:
		d.add(t)
ans = tmp + len(d) ** 2
ax = ans
for (t, dd) in S[K:]:
	if len(ds) == 0:
		break
	if t not in d:
		ax += 2 * len(d) + 1
		ax += dd - ds.pop()
		d.add(t)
		ans = max(ax, ans)
print(ans)


from heapq import heappop, heappush
(n, k) = (int(i) for i in input().split())
(x, y, z, q) = ([], set(), [0] * n, [])
for _ in range(n):
	(t, d) = (int(i) for i in input().split())
	x.append((d, t - 1))
(x, p) = (sorted(x)[::-1], 0)
for i in range(k):
	p += x[i][0]
	z[x[i][1]] += 1
	y.add(x[i][1])
	heappush(q, x[i])
(ans, m, l, F) = (p + len(y) ** 2, k, len(y), 1)
while F:
	F = 0
	while q:
		(d, t) = heappop(q)
		if z[t] != 1:
			(f, F, z[t]) = (1, 1, z[t] - 1)
			for j in range(m, n):
				if z[x[j][1]] == 0:
					(z[x[j][1]], m, f, l) = (1, j, 0, l + 1)
					p = p - d + x[j][0]
					break
			if f:
				F = 0
			else:
				ans = max(ans, p + l ** 2)
			break
print(ans)


(n, k) = map(int, input().split())
raw = [[] for _ in range(n)]
for _ in range(n):
	(t, d) = map(int, input().split())
	t -= 1
	raw[t].append(d)
only = []
other = []
for i in range(n):
	if len(raw[i]) != 0:
		raw[i].sort(reverse=True)
		only.append(raw[i][0])
		other += raw[i][1:]
only.sort(reverse=True)
only += [-10 ** 18 for _ in range(k)]
other.sort(reverse=True)
now = sum(only[:k])
can = [now + k * k]
for j in range(k):
	try:
		now -= only[k - 1 - j]
		now += other[j]
		can.append(now + (k - 1 - j) ** 2)
	except:
		break
print(max(can))


(n, k) = map(int, input().split())
A = []
for _ in range(n):
	A.append(list(map(int, input().split())))
A.sort(key=lambda x: x[1], reverse=True)
X = []
Y = []
st = set()
for i in range(k):
	(t, d) = A[i]
	if t in st:
		X.append(d)
	else:
		Y.append(d)
		st.add(t)
x = sum(X)
y = sum(Y)
v = len(Y)
ans = x + y + v ** 2
for i in range(k, n):
	if not X:
		break
	(t, d) = A[i]
	if t in st:
		continue
	st.add(t)
	x -= X.pop()
	y += d
	v += 1
	ans = max(ans, x + y + v ** 2)
print(ans)


import sys
readline = sys.stdin.readline
(n, k) = map(int, input().split())
A = []
for _ in range(n):
	(t, d) = map(int, readline().split())
	A.append((d, t))
A.sort(reverse=True)
X = []
Y = []
st = set()
for i in range(k):
	(d, t) = A[i]
	if t in st:
		X.append(d)
	else:
		Y.append(d)
		st.add(t)
x = sum(X)
y = sum(Y)
v = len(Y)
ans = x + y + v ** 2
for i in range(k, n):
	if not X:
		break
	(d, t) = A[i]
	if t in st:
		continue
	st.add(t)
	x -= X.pop()
	y += d
	v += 1
	ans = max(ans, x + y + v ** 2)
print(ans)


def main():
	(N, K) = map(int, input().split())
	TD = [tuple(map(int, input().split())) for _ in range(N)]
	TD.sort(key=lambda x: x[1], reverse=True)
	s = set()
	rep = []
	for (t, d) in TD[:K]:
		if t in s:
			rep.append(d)
		else:
			s.add(t)
	m = sum((d for (_, d) in TD[:K]))
	p = len(s) ** 2 + m
	for (t, d) in TD[K:]:
		if not rep:
			break
		if t in s:
			continue
		m += d - rep.pop()
		s.add(t)
		p = max(p, len(s) ** 2 + m)
	return p
print(main())


(n, k) = map(int, input().split())
INF = 10 ** 18
sushi = [[-INF] for _ in range(n)]
for _ in range(n):
	(t, d) = map(int, input().split())
	sushi[t - 1].append(d)
for i in range(n):
	sushi[i].sort(reverse=True)
sushi.sort(key=lambda x: x[0], reverse=True)
q = []
res = 0
for i in range(k):
	res += sushi[i][0]
	for j in sushi[i][1:]:
		q.append(j)
q.sort()
cur = res
res += k ** 2
for var in range(1, k)[::-1]:
	a = q.pop()
	b = sushi[var][0]
	cur += a - b
	res = max(res, cur + var ** 2)
print(res)


from collections import deque
(N, K) = map(int, input().split())
dt = []
for _ in range(N):
	(t, d) = map(int, input().split())
	dt.append((d, t))
dt.sort(reverse=True)
s = set()
bests = []
rems = deque()
for (d, t) in dt:
	if t in s:
		rems.append(d)
	else:
		s.add(t)
		bests.append(d)
	if len(bests) == K:
		break
x = len(bests)
k = x
p = sum(bests) + x * x
while k < K:
	p += rems.popleft()
	k += 1
maxp = p
while len(rems) and rems[0] > bests[-1]:
	p -= bests.pop() + x * x
	x -= 1
	p += rems.popleft() + x * x
	maxp = max(maxp, p)
print(maxp)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)
used = [0 for _ in range(N)]
dup = []
deli = 0
for i in range(K):
	(t, d) = sushi[i]
	if used[t - 1]:
		dup.append(d)
	used[t - 1] = 1
	deli += d
vari = sum(used)
sat = vari ** 2 + deli
dup.sort(reverse=True)
for i in range(N - K):
	if not dup:
		break
	(t, d) = sushi[K + i]
	if used[t - 1]:
		continue
	used[t - 1] = 1
	deli -= dup.pop()
	deli += d
	vari += 1
	sat = max(sat, vari ** 2 + deli)
print(sat)


from operator import itemgetter
from itertools import accumulate
(n, k) = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(n)]
sushi.sort(key=itemgetter(1))
sushi.reverse()
a = []
b = []
in_a = [0] * (n + 1)
for i in range(n):
	(t, d) = sushi[i]
	if in_a[t] == 0:
		in_a[t] = 1
		a.append(d)
	else:
		b.append(d)
ans = 0
a = list(accumulate([0] + a))
b = list(accumulate([0] + b))
for i in range(len(a)):
	if i <= k:
		if 0 <= k - i < len(b):
			ans = max(a[i] + b[k - i] + i ** 2, ans)
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
dtlist = []
tset_all = set()
for i in range(N):
	(t, d) = map(int, input().split())
	dtlist.append((d, t))
	tset_all.add(t)
dtlist.sort()
dtlist_Krev = []
dsum = 0
tdic = defaultdict(int)
for i in range(K):
	(d, t) = dtlist.pop()
	dtlist_Krev.append((d, t))
	dsum += d
	tdic[t] += 1
dtlist_Krev.sort(reverse=True)
t0 = len(tdic)
max_answer = dsum + t0 ** 2
for i in range(t0 + 1, min(K, len(tset_all)) + 1):
	loop_flg = True
	while loop_flg:
		(d, t) = dtlist_Krev.pop()
		if tdic[t] > 1:
			tdic[t] -= 1
			dsum -= d
			while True:
				(d2, t2) = dtlist.pop()
				if tdic[t2] == 0:
					tdic[t2] = 1
					dsum += d2
					loop_flg = False
					break
	answer_i = dsum + i ** 2
	max_answer = max(max_answer, answer_i)
print(max_answer)


a = list(map(lambda x: int(x), input().split()))
N = a[0]
K = a[1]
sushis = []
for i in range(0, N):
	sushis.append(list(map(lambda x: int(x), input().split())))
sushis.sort(key=lambda x: x[1], reverse=True)
netas = set()
duplicates = []
choices = sushis[:K]
for choice in choices:
	if choice[0] in netas:
		duplicates.append(choice[1])
	else:
		netas.add(choice[0])
p = sum(map(lambda x: x[1], choices)) + len(netas) ** 2
answer = p
for sushi in sushis[K:]:
	if sushi[0] not in netas and duplicates:
		netas.add(sushi[0])
		duplicate = duplicates.pop()
		p += sushi[1] - duplicate + 2 * len(netas) - 1
		answer = max(answer, p)
print(answer)


(N, K) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)
score = 0
remains = []
kinds = set()
for (t, d) in sushi[:K]:
	if t in kinds:
		remains.append(d)
	kinds.add(t)
	score += d
score += len(kinds) ** 2
test = score
for (t, d) in sushi[K:]:
	if not remains:
		break
	if t in kinds:
		continue
	kinds.add(t)
	rm = remains.pop()
	test = test + (d - rm) + (len(kinds) * 2 - 1)
	score = max(score, test)
print(score)


(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
td.sort(key=lambda x: x[1], reverse=True)
cand = []
memo = [0 for i in range(n + 1)]
ans = 0
duplicate = []
unique = []
num = 0
i = 0
for (t, d) in td:
	i += 1
	if i <= k:
		ans += d
		if memo[t]:
			duplicate.append(d)
		else:
			memo[t] = 1
			num += 1
	elif not memo[t]:
		unique.append(d)
		memo[t] = 1
tmp = ans
ans += num * num
for (d, u) in zip(reversed(duplicate), unique):
	tmp += u - d
	num += 1
	ans = max(ans, tmp + num * num)
print(ans)


from heapq import heappush, heappop
(N, K, *L) = map(int, open(0).read().split())
ls = []
for (t, d) in zip(*[iter(L)] * 2):
	ls += [(d, t)]
used = []
cnt = {}
hq = []
S = set()
ls.sort(reverse=True)
m = 0
for i in range(K):
	(d, t) = ls[i]
	cnt[t] = cnt.get(t, 0) + 1
	m += d
	if cnt[t] > 1:
		heappush(used, (d, t))
	S.add(t)
m += len(S) ** 2
for i in range(K, N):
	(d, t) = ls[i]
	if t not in S:
		heappush(hq, (-d, t))
ans = m
while used:
	(d, t) = heappop(used)
	while hq:
		if hq[0][1] not in S:
			break
		heappop(hq)
	else:
		break
	m -= d
	(n, s) = heappop(hq)
	m += -n + 2 * len(S) + 1
	ans = max(ans, m)
	S.add(s)
print(ans)


import heapq
(N, K) = map(int, input().split())
sushi = []
for i in range(N):
	(t, d) = map(int, input().split())
	heapq.heappush(sushi, (-d, t))
total = 0
types = set()
remain = []
for i in range(K):
	(d, t) = heapq.heappop(sushi)
	total -= d
	if t not in types:
		types.add(t)
	else:
		heapq.heappush(remain, -d)
types_len = len(types)
ans = total + types_len ** 2
while sushi and remain:
	(d, t) = heapq.heappop(sushi)
	if t not in types:
		types.add(t)
		remain_d = heapq.heappop(remain)
		total = total - d - remain_d
		types_len += 1
		ans = max(ans, total + types_len ** 2)
print(ans)


from collections import Counter
(N, K) = map(int, input().split())
t_d = []
for _ in range(N):
	(t, d) = map(int, input().split())
	t_d.append([t, d])
t_d = sorted(t_d, key=lambda x: -x[1])
kiso = 0
neta = Counter()
stack = []
for (t, d) in t_d[:K]:
	kiso += d
	neta[t] += 1
	stack.append((t, d))
ans = kiso + len(neta) ** 2
tmp = ans
for (t, d) in t_d[K:]:
	if t in neta:
		continue
	while stack:
		(t0, d0) = stack.pop()
		if neta[t0] > 1:
			tmp += d - d0 + 2 * len(neta) + 1
			ans = max(ans, tmp)
			neta[t0] -= 1
			neta[t] += 1
			break
	else:
		break
print(ans)


from collections import deque
(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
res = 0
td.sort(key=lambda x: -x[1])
kind = set()
queue = deque()
for (t, d) in td[:k]:
	if t in kind:
		queue.append(d)
	else:
		kind.add(t)
	res += d
ans = res + len(kind) ** 2
point = ans
count = len(queue)
for (t, d) in td[k:n]:
	if count == 0:
		break
	if not t in kind:
		point += -queue.pop() + d + len(kind) * 2 + 1
		kind.add(t)
		ans = max(ans, point)
		count -= 1
print(ans)


import sys
sys.setrecursionlimit(100000000)

def main():
	(N, K) = map(int, input().split())
	sushi = [tuple(map(int, input().split())) for _ in range(N)]
	sushi.sort(key=lambda x: x[1], reverse=True)
	ans = 0
	dic = {}
	change = []
	for (a, b) in sushi[:K]:
		if a in dic:
			dic[a].append(b)
			change.append((a, b))
		else:
			dic[a] = [b]
		ans += b
	various = len(dic)
	ans += various ** 2
	ret = ans
	used_type = set(dic.keys())
	suggestion = [p for p in sushi[K:] if p[0] not in used_type]
	for (a, b) in suggestion:
		if len(change) == 0:
			break
		if a in used_type:
			continue
		dic[change[-1][0]].pop()
		ret -= change[-1][1]
		ret += b + 2 * various + 1
		dic[a] = b
		change.pop()
		various += 1
		used_type.add(a)
		ans = max(ans, ret)
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
from collections import defaultdict
from itertools import accumulate
input = sys.stdin.readline
(N, K) = map(int, input().split())
sushi = defaultdict(list)
for i in range(N):
	(t, d) = map(int, input().split())
	sushi[t].append(d)
(X, Y) = ([], [])
for v in sushi.values():
	v = sorted(v, reverse=True)
	X.append(v[0])
	if len(v) > 1:
		Y += v[1:]
X = sorted(X, reverse=True)
Y = sorted(Y, reverse=True)
X = [0] + [x for x in accumulate(X)]
Y = [0] + [x for x in accumulate(Y)]
ans = 0
for i in range(1, min(len(X), K + 1)):
	j = K - i
	if j < len(Y):
		ans = max(ans, X[i] + Y[j] + i * i)
print(ans)


import sys
from operator import itemgetter
from heapq import *
input = sys.stdin.readline

def main():
	(n, k) = list(map(int, input().split()))
	sushi = [list(map(int, input().split())) for _ in range(n)]
	sushi.sort(key=itemgetter(1), reverse=True)
	key = []
	already = [False] * (n + 1)
	variety = k
	taste = 0
	for i in range(k):
		(v, t) = sushi[i]
		taste += t
		if already[v]:
			variety -= 1
			heappush(key, t)
			continue
		already[v] = True
	ans = [variety ** 2 + taste]
	for i in range(k, n):
		if variety == k:
			break
		(v, t) = sushi[i]
		if already[v]:
			continue
		already[v] = True
		taste += t - key[0]
		heappop(key)
		variety += 1
		ans.append(variety ** 2 + taste)
	print(max(ans))

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for i in range(n)]
td.sort(key=lambda x: x[1], reverse=True)
a = 0
ans = []
kind = [-1] * n
c = 0
min_p = []
for i in range(n):
	eat = False
	if i < k:
		a += td[i][1]
		eat = True
	elif min_p:
		if kind[td[i][0] - 1] < 0:
			a -= min_p.pop() - td[i][1]
			a += (c + 1) ** 2 - c ** 2
			ans.append(a)
			eat = True
	if eat:
		if kind[td[i][0] - 1] < 0:
			kind[td[i][0] - 1] = 1
			c += 1
		else:
			min_p.append(td[i][1])
	if i == k - 1:
		a += c ** 2
		ans.append(a)
print(max(ans))


from collections import defaultdict
(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda A: A[1], reverse=True)
A = TD[:K][::-1]
cnt = defaultdict(int)
V = set()
dSum = 0
for (t, d) in A:
	dSum += d
	cnt[t] += 1
	V.add(t)
i = 0
ans = dSum + len(V) ** 2
for (t, d) in TD[K:]:
	if not t in V:
		while i < K and cnt[A[i][0]] <= 1:
			i += 1
		if i == K:
			break
		dSum = dSum - A[i][1] + d
		V.add(t)
		cnt[A[i][0]] -= 1
		i += 1
		ans = max(ans, dSum + len(V) ** 2)
print(ans)


import sys
try:
	from typing import List
except ImportError:
	pass

def solve(N: int, K: int, t: 'List[int]', d: 'List[int]'):
	ss = sorted(zip(d, t), reverse=True)
	gs = []
	mst = set()
	for (di, ti) in ss[:K]:
		if ti in mst:
			gs.append((di, ti))
		else:
			mst.add(ti)
	dm = {}
	for (di, ti) in ss[K:]:
		if ti in dm or ti in mst:
			continue
		dm[ti] = di
	hs = sorted(((di, ti) for (ti, di) in list(dm.items())), reverse=True)
	cd = sum((di for (di, ti) in ss[:K]))
	ct = len(mst)
	m = cd + ct * ct
	for ((gdi, gti), (hdi, hti)) in zip(reversed(gs), hs):
		cd += hdi - gdi
		ct += 1
		m = max(m, cd + ct * ct)
	print(m)

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	K = int(next(tokens))
	t = [int()] * N
	d = [int()] * N
	for i in range(N):
		t[i] = int(next(tokens))
		d[i] = int(next(tokens))
	solve(N, K, t, d)

def __starting_point():
	main()
__starting_point()


from heapq import heappush, heappop
(N, K) = map(int, input().split())
log = [0] * N
pre = []
ls = []
for i in range(N):
	(t, d) = map(int, input().split())
	t = t - 1
	heappush(ls, (-d, t))
v = 0
n = 0
for i in range(K):
	(d, t) = heappop(ls)
	d = -d
	log[t] += 1
	v += d
	if log[t] > 1:
		heappush(pre, (d, t))
	else:
		n += 1
v += n * n
ans = v
while ls and pre:
	(d, t) = heappop(ls)
	if log[t] > 0:
		continue
	log[t] += 1
	d = -d
	pv = v
	(x, y) = heappop(pre)
	v -= x
	v += d
	v += 2 * n + 1
	n += 1
	if ans < v:
		ans = v
print(ans)


from collections import defaultdict

def main():
	(n, k) = list(map(int, input().split()))
	td = []
	for i in range(n):
		(ti, di) = list(map(int, input().split()))
		td.append((ti, di))
	td = list(reversed(sorted(td)))
	tdd = defaultdict(list)
	for (t, d) in td:
		tdd[t].append(d)
	a = []
	b = []
	for (_, v) in list(tdd.items()):
		a.append(v[0])
		b += v[1:]
	a = list(reversed(sorted(a)))
	b = list(reversed(sorted(b)))
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	for i in range(len(a)):
		a[i] += (i + 1) ** 2
	for i in range(1, len(b)):
		b[i] += b[i - 1]
	a = [0] + a
	b = [0] + b
	res = 0
	for i in range(1, k + 1):
		if i >= len(a) or k - i >= len(b):
			continue
		ts = a[i] + b[k - i]
		res = max(res, ts)
	print(res)

def __starting_point():
	main()
__starting_point()


def main():
	from collections import deque
	(n, k, *td) = list(map(int, open(0).read().split()))
	s = list(zip(*[iter(td)] * 2))
	t = sorted(s, key=lambda x: x[1], reverse=True)
	variety = set()
	base = 0
	duplicated = deque([])
	for (x, y) in t[:k]:
		base += y
		if x in variety:
			duplicated.append(y)
		else:
			variety.add(x)
	now = base + len(variety) ** 2
	nx = deque(t[k:])
	c = len(variety)
	tmp = now
	while c < k and nx:
		(i, j) = nx.popleft()
		if i in variety:
			continue
		d = duplicated.pop()
		dif = j - d + 2 * c + 1
		variety.add(i)
		tmp = max(tmp, now + dif)
		now += dif
		c += 1
	print(tmp)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)
point = 0
stack = []
kind = set()
for (t, d) in sushi[:K]:
	point += d
	if t in kind:
		stack.append(d)
	else:
		kind.add(t)
point += len(kind) ** 2
ans = point
for (t, d) in sushi[K:]:
	if not stack:
		break
	if t not in kind:
		point += d - stack.pop() + 2 * len(kind) + 1
		kind.add(t)
		ans = max(ans, point)
print(ans)


import heapq
(N, K) = map(int, input().split())
S = [[] for _ in range(N)]
E = [0] * N
Q = []
D = []
x = 0
k = 0
h = 0
for i in range(N):
	(t, d) = map(int, input().split())
	S[i] = [d, t]
S.sort(reverse=True)
for (d, t) in S:
	if E[t - 1] > 0:
		D.append(d)
	elif k < K:
		E[t - 1] += 1
		heapq.heappush(Q, d)
		x += 1
		k += 1
		h += d
h += x ** 2
for d in D:
	if k < K:
		heapq.heappush(Q, d)
		h += d
		k += 1
		continue
	q = heapq.heappop(Q)
	if d <= q:
		break
	_h = h - q - x ** 2 + d + (x - 1) ** 2
	if _h < h:
		break
	heapq.heappush(Q, d)
	x -= 1
	h = _h
print(h)


(N, K) = map(int, input().split())
a = []
for i in range(N):
	(t, d) = map(int, input().split())
	a.append((t, d))
a.sort(key=lambda x: x[1], reverse=True)
vmax = 0
s = set()
q = []
for i in range(K):
	vmax += a[i][1]
	if a[i][0] in s:
		q.append(a[i][1])
	s.add(a[i][0])
vmax += len(s) ** 2
i += 1
v = vmax
while i < N and q:
	if a[i][0] not in s:
		v -= q.pop() + len(s) ** 2
		v += a[i][1] + (len(s) + 1) ** 2
		vmax = max(vmax, v)
		s.add(a[i][0])
	i += 1
print(vmax)


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, K) = lr()
TD = [lr() for _ in range(N)]
TD.sort(key=lambda x: x[1], reverse=True)
used = set()
overlap = []
for (t, d) in TD[:K]:
	if t in used:
		overlap.append(d)
	else:
		used.add(t)
delicious = sum([x[1] for x in TD[:K]])
answer = delicious + len(used) ** 2
for i in range(K, N):
	if not overlap:
		break
	if TD[i][0] in used:
		continue
	delicious += TD[i][1] - overlap.pop()
	used.add(TD[i][0])
	if answer < delicious + len(used) ** 2:
		answer = delicious + len(used) ** 2
print(answer)


import heapq
(N, K) = map(int, input().split())
dt = [list(map(int, input().split()))[::-1] for i in range(N)]
dt.sort(reverse=True)
ans = 0
t_set = set()
candidates = []
for (d, t) in dt[:K]:
	if t in t_set:
		heapq.heappush(candidates, [d, t])
		ans += d
	else:
		t_set.add(t)
		ans += d
x = len(t_set)
ans += x ** 2
if len(candidates) == 0:
	print(ans)
	quit()
ans = [ans]
for (d, t) in dt[K:]:
	if t in t_set:
		continue
	(cand_d, cand_t) = heapq.heappop(candidates)
	_ans = ans[-1] - cand_d + d + (2 * x + 1)
	x += 1
	ans.append(_ans)
	t_set.add(t)
	if len(candidates) == 0:
		break
print(max(ans))


(N, K) = map(int, input().split())
top = [0] * N
sub = []
for _ in range(N):
	(t, d) = map(int, input().split())
	t -= 1
	if top[t] == 0:
		top[t] = d
	elif top[t] >= d:
		sub.append(d)
	else:
		sub.append(top[t])
		top[t] = d
top.sort(reverse=True)
sub.sort(reverse=True)
res = [0]
for i in range(N):
	if top[i] != 0:
		res.append(res[-1] + top[i])
	else:
		res.append(-1)
w = [0]
for i in range(len(sub)):
	w.append(w[-1] + sub[i])
ans = 0
for i in range(1, K + 1):
	if len(w) - 1 >= K - i and res[i] != -1:
		ans = max(res[i] + w[K - i] + i ** 2, ans)
print(ans)


from operator import itemgetter
from functools import reduce
(N, K) = map(int, input().split())
(t, d) = zip(*(map(int, input().split()) for _ in range(N)))
fn = itemgetter(0)
fd = itemgetter(1)
ss = sorted(zip(t, d), key=fd, reverse=True)
netas = set()
duplicates = []
for s in ss[:K]:
	if s[0] in netas:
		duplicates.append(s[1])
	else:
		netas.add(s[0])
p = sum(map(fd, ss[:K])) + len(netas) ** 2
ans = p
for s in ss[K:]:
	if s[0] not in netas and duplicates:
		netas.add(s[0])
		duplicate = duplicates.pop()
		p += s[1] - duplicate + 2 * len(netas) - 1
		ans = max(ans, p)
print(ans)


(N, K) = map(int, input().split())
td = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: -x[1])
answer = 0
number = set()
afterpop = []
for i in range(K):
	answer += td[i][1]
	if td[i][0] not in number:
		number.add(td[i][0])
	else:
		afterpop.append(td[i][1])
answer += len(number) ** 2
index = K
tempanswer = answer
while index < N and afterpop:
	if td[index][0] not in number:
		number.add(td[index][0])
		tempanswer = tempanswer + td[index][1] - afterpop.pop() - (len(number) - 1) ** 2 + len(number) ** 2
		answer = max(tempanswer, answer)
	index += 1
print(answer)


import heapq
(N, K) = map(int, input().split())
TD = [[int(x) for x in input().split()] for y in range(N)]
TD = sorted(TD, key=lambda x: -x[1])
ans = 0
neta = set([])
rep_neta = []
for i in range(K):
	(a, b) = TD[i]
	if not a in neta:
		neta.add(a)
		ans += b
	else:
		ans += b
		rep_neta.append(b)
ans += len(neta) ** 2
cnt = ans
for i in range(K, N):
	if len(rep_neta) == 0:
		break
	else:
		(a, b) = TD[i]
		if not a in neta:
			cnt += 2 * len(neta) + 1
			cnt += b - rep_neta.pop(-1)
			neta.add(a)
			ans = max(ans, cnt)
print(ans)


(N, K) = map(int, input().split())
td = []
for i in range(N):
	(t, d) = map(int, input().split())
	td.append([t, d])
td.sort(key=lambda x: x[1], reverse=True)
A = td[:K]
B = []
s2 = set()
for (i, j) in td[K:]:
	if not i in s2:
		s2.add(i)
		B.append([i, j])
s1 = set()
n = 0
C = []
sum = 0
for (i, j) in A:
	if not i in s1:
		s1.add(i)
		n += 1
		sum += j
	else:
		C.append([i, j])
		sum += j
sum += n ** 2
B.reverse()
D = []
for (i, j) in B:
	if not i in s1:
		D.append([i, j])
list = [sum]
while C:
	if D:
		(i, j) = D.pop()
		list.append(list[-1] + 2 * n + 1 + (j - C[-1][1]))
		n += 1
	C.pop()
print(max(list))


from operator import itemgetter
(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
td.sort(key=itemgetter(1), reverse=True)
ans = 0
kind = 0
flg = [False] * n
(sing, comp) = ([], [])
for i in range(n):
	(t, d) = td[i]
	t -= 1
	if i < k:
		ans += d
		if flg[t]:
			comp.append(d)
		else:
			flg[t] = True
			kind += 1
	elif not flg[t]:
		sing.append(d)
		flg[t] = True
comp = comp[::-1]
cnt = ans
ans += kind ** 2
if len(comp) > len(sing):
	for i in range(len(sing)):
		(dc, ds) = (comp[i], sing[i])
		cnt += ds - dc
		kind += 1
		ans = max(ans, cnt + kind ** 2)
else:
	for i in range(len(comp)):
		(dc, ds) = (comp[i], sing[i])
		cnt += ds - dc
		kind += 1
		ans = max(ans, cnt + kind ** 2)
print(ans)


(N, K) = map(int, input().split())
b = []
for _ in range(N):
	(t, d) = map(int, input().split())
	b.append([t, d])
b.sort(key=lambda x: -x[1])
f = [0] * (N + 1)
x = 0
point = 0
for [t, d] in b[:K]:
	if f[t] == 0:
		x += 1
	f[t] += 1
	point += d
maxpoint = point + x * x
h = K - 1
for [t, d] in b[K:]:
	if f[t] == 0:
		f[t] = 1
		x += 1
		point += d
		for i in range(h, -2, -1):
			if i == -1:
				print(maxpoint)
				exit()
			t = b[i][0]
			d = b[i][1]
			if f[t] > 1:
				f[t] -= 1
				point -= d
				h = i - 1
				break
		maxpoint = max(maxpoint, point + x * x)
print(maxpoint)


(n, k) = map(int, input().split())
a = []
for _ in range(n):
	a.append(tuple(list(map(int, input().split()))[::-1]))
a.sort(reverse=1)
(x, y) = ([], [])
s = set()
for i in range(k):
	(d, t) = a[i]
	if t in s:
		x.append(d)
	else:
		y.append(d)
		s.add(t)
(xx, yy, v) = (sum(x), sum(y), len(y))
ans = xx + yy + v ** 2
for i in range(k, n):
	if len(x) == 0:
		break
	(d, t) = a[i]
	if t in s:
		continue
	s.add(t)
	xx -= x.pop()
	yy += d
	v += 1
	ans = max(ans, xx + yy + v ** 2)
print(ans)


(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
td = sorted(td, key=lambda x: -x[1])
dict_td = set()
q = []
ans = 0
for i in range(k):
	if td[i][0] in dict_td:
		q.append(td[i])
	ans += td[i][1]
	dict_td.add(td[i][0])
ans += len(dict_td) ** 2
tmp_ans = ans
for i in range(k, n):
	if len(q) == 0:
		break
	if td[i][0] not in dict_td:
		minus = q.pop()
		tmp_ans += td[i][1] - minus[1]
		dict_len = len(dict_td)
		tmp_ans += (dict_len + 1) ** 2 - dict_len ** 2
		dict_td.add(td[i][0])
	ans = max(tmp_ans, ans)
print(ans)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
top = [0] * n
sub = []
for i in range(n):
	(t, d) = list(map(int, input().split()))
	t -= 1
	if top[t] == 0:
		top[t] = d
	elif d > top[t]:
		sub.append(top[t])
		top[t] = d
	else:
		sub.append(d)
top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]
for p in top:
	if p == 0:
		top_sum.append(-1)
	else:
		top_sum.append(top_sum[-1] + p)
for p in sub:
	sub_sum.append(sub_sum[-1] + p)
ans = 0
for i in range(1, k + 1):
	if len(sub_sum) - 1 >= k - i and top_sum[i] != -1:
		ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)
print(ans)


(n, k) = map(int, input().split())
nai = [list(map(int, input().split())) for _ in range(n)]
nai = sorted(nai, key=lambda x: -x[1])
ans = 0
aru = []
spe = set()
m = 0
for i in range(k):
	anstmp = nai.pop(0)
	if anstmp[0] not in spe:
		ans += anstmp[1]
		spe.add(anstmp[0])
	else:
		aru.append(anstmp[1])
sumaru = sum(aru)
m = ans + sumaru + len(spe) ** 2
for i in range(len(nai)):
	if len(aru) == 0:
		break
	if nai[i][0] not in spe:
		sumaru -= aru.pop()
		ans += nai[i][1]
		spe.add(nai[i][0])
	m = max(m, ans + sumaru + len(spe) ** 2)
print(m)


(N, K) = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(N)]
t.sort(key=lambda x: -x[1])
ans = 0
dp = set()
p = []
for i in range(K):
	ans += t[i][1]
	if t[i][0] in dp:
		p.append(t[i][1])
	dp.add(t[i][0])
ans += len(dp) ** 2
wer = ans
while K < N and p:
	if t[K][0] not in dp:
		wer = wer + t[K][1] - p.pop() - len(dp) ** 2 + (len(dp) + 1) ** 2
		ans = max(ans, wer)
		dp.add(t[K][0])
	K += 1
print(ans)


def main():
	(n, k) = map(int, input().split())
	sushi = [list(map(int, input().split())) for _ in range(n)]
	sushi.sort(key=lambda x: x[1], reverse=True)
	ans = 0
	t = [0] * (n + 1)
	tmp = 0
	cnt = 0
	for i in range(k):
		ans += sushi[i][1]
		if t[sushi[i][0]] == 0:
			cnt += 1
		tmp += sushi[i][1]
		t[sushi[i][0]] += 1
	ans = tmp + cnt * cnt
	p = k
	for i in range(k, n):
		f = False
		if t[sushi[i][0]] == 0:
			f = True
			for j in reversed(range(p)):
				if 1 < t[sushi[j][0]]:
					t[sushi[j][0]] -= 1
					t[sushi[i][0]] += 1
					tmp -= sushi[j][1]
					tmp += sushi[i][1]
					p = j
					cnt += 1
					ans = max(ans, tmp + cnt * cnt)
					f = False
					break
		if f:
			break
	print(ans)

def __starting_point():
	main()
__starting_point()


def IL():
	return list(map(int, input().split()))

def SL():
	return input().split()

def I():
	return int(input())

def S():
	return input()
(n, k) = IL()
top = dict()
sub = []
for i in range(n):
	(t, d) = IL()
	if t in top:
		sub.append(min(top[t], d))
		top[t] = max(top[t], d)
	else:
		top[t] = d
top = sorted(top.items(), key=lambda x: -x[1])
sub.sort(reverse=True)
rtop = [top[0][1]]
rsub = [0]
for i in range(1, len(top)):
	rtop.append(rtop[-1] + top[i][1])
for i in range(len(sub)):
	rsub.append(rsub[-1] + sub[i])
ans = 0
for i in range(k):
	if i < len(rtop) and 0 <= k - i - 1 < len(rsub):
		ans = max(ans, rtop[i] + rsub[k - i - 1] + (i + 1) ** 2)
print(ans)


(n, k) = list(map(int, input().split()))
sushi = []
for i in range(n):
	sushi.append(list(map(int, input().split())))
point = 0
sushi_kind = set()
duplication = []
sushi.sort(key=lambda x: x[1], reverse=True)
for i in range(k):
	point += sushi[i][1]
	if sushi[i][0] in sushi_kind:
		duplication.append(sushi[i])
	else:
		sushi_kind.add(sushi[i][0])
ans = point + pow(len(sushi_kind), 2)
dup_index = len(duplication) - 1
for i in range(k, n):
	if sushi[i][0] in sushi_kind:
		continue
	elif dup_index >= 0:
		point -= duplication[dup_index][1]
		dup_index -= 1
		point += sushi[i][1]
		sushi_kind.add(sushi[i][0])
	ans = max(ans, point + pow(len(sushi_kind), 2))
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda x: x[1], reverse=True)
ans = 0
s = set()
r = list()
for i in range(K):
	(t, d) = TD[i]
	ans += d
	if t not in s:
		s.add(t)
	else:
		r.append(TD[i])
ans += len(s) ** 2
Ans = ans
for i in range(K, N):
	(t0, d0) = TD[i]
	if t0 not in s and len(r) > 0:
		(t1, d1) = r.pop()
		ans = ans - d1 + d0 - len(s) ** 2 + (len(s) + 1) ** 2
		s.add(t0)
		Ans = max(Ans, ans)
print(Ans)


from heapq import heappush, heappop, heapreplace
INF = 10 ** 9 + 5
(N, K, *TD) = map(int, open(0).read().split())
E = [[] for _ in range(N)]
for (t, d) in zip(*[iter(TD)] * 2):
	E[t - 1].append(d)
for e in E:
	if e:
		e.sort(reverse=True)
	else:
		e.append(-INF)
E.sort(key=lambda x: -x[0])
cur = 0
Q = []
for ei in E[:K]:
	cur += ei[0]
	for eij in ei[1:]:
		heappush(Q, -eij)
for ei in E[K:]:
	for eij in ei:
		heappush(Q, -eij)
res = cur + K * K
for x in reversed(range(1, K)):
	(v, w) = (E[x][0], -Q[0])
	if v < w:
		heappop(Q)
		cur += w
		heappush(Q, -v)
		cur -= v
	res = max(res, cur + x * x)
print(res)


from collections import Counter
(N, K) = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(reverse=True, key=lambda a: a[1])
A = TD[:K]
B = []
V = set()
for (t, d) in TD:
	if t in V:
		continue
	B.append((t, d))
	V.add(t)
cntT = Counter([t for (t, _) in A])
V = set(cntT.keys())
S = sum([d for (_, d) in A])
B = [(t, d) for (t, d) in B if not t in V]
C = []
for (t, d) in A[::-1]:
	if cntT[t] > 1:
		C.append((t, d))
		cntT[t] -= 1
C = C[::-1]
ans = S + len(V) ** 2
for (t, d) in B:
	if not C:
		break
	(_, less) = C.pop()
	S -= less
	S += d
	V.add(t)
	ans = max(ans, S + len(V) ** 2)
print(ans)


from collections import Counter
from heapq import heappush, heappop
(n, k) = list(map(int, input().split()))
s = []
for _ in range(n):
	(t, d) = list(map(int, input().split()))
	s.append((d, t))
s.sort()
bp = 0
x = 0
c = Counter()
cand = []
for _ in range(k):
	(d, t) = s.pop()
	bp += d
	if c[t] == 0:
		x += 1
	c[t] += 1
	heappush(cand, (d, t))
ans = bp + x * x
while s:
	(d, t) = s.pop()
	if c[t] == 0:
		while cand:
			(dd, td) = heappop(cand)
			if c[td] == 1:
				continue
			else:
				c[td] -= 1
				bp -= dd
				break
		else:
			break
		bp += d
		x += 1
		c[t] = 1
		ans = max(ans, bp + x * x)
print(ans)


(n, k) = map(int, input().split())
td = []
for _ in range(n):
	td.append(list(map(int, input().split())))
td.sort(key=lambda x: x[1], reverse=True)
NEW = [1] * (n + 1)
x = 0
y = 0
TOP = []
SUB = []
A = []
for tdi in td[:k]:
	if NEW[tdi[0]] == 1:
		NEW[tdi[0]] = 0
		TOP.append(tdi[1])
		y += 1
	else:
		A.append(tdi[1])
	x += tdi[1]
for tdi in td[k:]:
	if NEW[tdi[0]] == 1:
		SUB.append(tdi[1])
		NEW[tdi[0]] = 0
ans = x + y ** 2
for i in range(min(k - 1, len(A), len(SUB))):
	x -= A.pop()
	x += SUB[i]
	y += 1
	ans = max(ans, x + y ** 2)
print(ans)


from collections import defaultdict
import heapq
(N, K) = map(int, input().split())
hq = []
tset_all = set()
for i in range(N):
	(t, d) = map(int, input().split())
	heapq.heappush(hq, (-d, t))
	tset_all.add(t)
hq_K = []
dsum = 0
tdic = defaultdict(int)
for i in range(K):
	(md, t) = heapq.heappop(hq)
	heapq.heappush(hq_K, (-md, t))
	dsum -= md
	tdic[t] += 1
t0 = len(tdic)
max_answer = dsum + t0 ** 2
for i in range(t0 + 1, min(K, len(tset_all)) + 1):
	loop_flg = True
	while loop_flg:
		(d, t) = heapq.heappop(hq_K)
		if tdic[t] > 1:
			tdic[t] -= 1
			dsum -= d
			while True:
				(md2, t2) = heapq.heappop(hq)
				if tdic[t2] == 0:
					tdic[t2] = 1
					dsum -= md2
					loop_flg = False
					break
	answer_i = dsum + i ** 2
	max_answer = max(max_answer, answer_i)
print(max_answer)


import heapq
(n, k) = map(int, input().split())
data = []
for i in range(n):
	(t, d) = map(int, input().split())
	data.append((-d, t))
data = sorted(data)
neta = set()
que1 = []
(p, x) = (0, 0)
for i in range(k):
	if data[i][1] in neta:
		heapq.heappush(que1, (-data[i][0], data[i][1]))
		x -= data[i][0]
	else:
		x -= data[i][0]
		p += 1
		neta.add(data[i][1])
mx = x + p * p
for i in range(k, n):
	if data[i][1] in neta:
		pass
	elif que1:
		a = heapq.heappop(que1)
		x = x - a[0] - data[i][0]
		p += 1
		neta.add(data[i][1])
		mx = max(mx, x + p * p)
	else:
		break
print(mx)


(n, k) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
td = sorted(td, key=lambda x: x[1], reverse=True)
eat_types = set()
sushi_dup = []
value = 0
for (t, d) in td[:k]:
	if not t in eat_types:
		eat_types.add(t)
	else:
		sushi_dup.append(d)
	value += d
ans = value + len(eat_types) ** 2
for (t, d) in td[k:]:
	if len(sushi_dup) == 0:
		break
	if t in eat_types:
		continue
	else:
		eat_types.add(t)
		r = sushi_dup.pop()
		value += d - r
		ans = max(ans, value + len(eat_types) ** 2)
print(ans)


(n, k) = map(int, input().split())
td = [list(map(int, input().split()))[::-1] for _ in range(n)]
td.sort(reverse=1)
s = set()
ss = set()
a = []
b = []
c = []
for i in range(n):
	if i < k:
		(d, t) = td[i]
		if t in s:
			b.append(d)
		else:
			a.append(d)
			s.add(t)
			ss.add(t)
	else:
		(d, t) = td[i]
		if t not in ss:
			c.append(d)
			ss.add(t)
c = c[::-1]
ls = len(s)
su = sum(a) + sum(b)
ans = ls * ls + su
for i in range(min(len(b), len(c))):
	ls += 1
	su -= b.pop()
	su += c.pop()
	ans = max(ans, ls * ls + su)
print(ans)


(n, k) = map(int, input().split())
top = [0] * n
sub = []
for i in range(n):
	(t, d) = map(int, input().split())
	t -= 1
	if top[t] == 0:
		top[t] = d
	elif top[t] >= d:
		sub.append(d)
	else:
		sub.append(top[t])
		top[t] = d
top.sort()
top = top[::-1]
res = [0]
for i in range(n):
	if top[i] != 0:
		res.append(res[-1] + top[i])
	else:
		res.append(-1)
sub.sort()
sub = sub[::-1]
w = [0]
for i in range(len(sub)):
	w.append(w[-1] + sub[i])
tmp = 0
for i in range(1, k + 1):
	if len(w) - 1 >= k - i and res[i] != -1:
		tmp = max(res[i] + w[k - i] + i * i, tmp)
print(tmp)


import heapq as h
I = lambda : list(map(int, input().split()))
(n, k) = I()
z = [i * 2 + 1 for i in range(n)]
s = sorted([I() for _ in [0] * n], key=lambda x: -x[1])
q = []
v = A = 0
l = [0] * -~n
for a in s[:k]:
	if l[a[0]]:
		h.heappush(q, a[1])
	else:
		A += z[v]
		v += 1
	l[a[0]] = 1
	A += a[1]
T = A
for a in s[k:]:
	if not q:
		break
	if l[a[0]] ^ 1:
		l[a[0]] = 1
		t = h.heappop(q)
		T = T - t + a[1] + z[v]
		v += 1
		A = max(A, T)
print(A)


import itertools
(N, K) = [int(_) for _ in input().split()]
TD = sorted([[int(_) for _ in input().split()] for _ in range(N)], key=lambda x: -x[1])
neta = set()
dupl = []
ans = [0]
for (t, d) in TD[:K]:
	ans[0] += d
	if t in neta:
		dupl += [d]
	else:
		neta.add(t)
x = len(neta)
ans[0] += x ** 2
for (t, d) in TD[K:]:
	if not t in neta and dupl:
		neta.add(t)
		ans += [ans[-1] - x ** 2 + (x + 1) ** 2 - dupl.pop() + d]
		x += 1
print(max(ans))


import heapq
(n, k) = (int(x) for x in input().split())
arr = []
discard = []
type = set()
score = 0
for i in range(n):
	(a, b) = (int(x) for x in input().split())
	heapq.heappush(arr, (-b, a))
for i in range(k):
	(d, t) = heapq.heappop(arr)
	score -= d
	if t not in type:
		type.add(t)
	else:
		heapq.heappush(discard, (-d, t))
bonus = len(type)
ans = score + bonus ** 2
while arr and discard:
	(pd, pt) = heapq.heappop(arr)
	if pt not in type:
		(_pd, _pt) = heapq.heappop(discard)
		type.add(pt)
		score = score - _pd - pd
		bonus += 1
		tmp = score + bonus ** 2
		ans = max(ans, tmp)
print(ans)


import sys
from heapq import *
input = sys.stdin.readline
(N, K) = map(int, input().split())
(D, H, var, res, L) = ([], [], set(), 0, N.bit_length() + 2)
for _ in range(N):
	(t, d) = map(int, input().split())
	D.append((d << L) + t)
D.sort(reverse=True)
for z in D[:K]:
	(d, t) = (z >> L, z % (1 << L))
	if t not in var:
		var.add(t)
	else:
		heappush(H, d)
	res += d
x = len(var)
res += x ** 2
tmp = res
for z in D[K:]:
	(d, t) = (z >> L, z % (1 << L))
	if H and t not in var:
		tmp += d - heappop(H) + 2 * x + 1
		x += 1
		var.add(t)
		res = max(res, tmp)
print(res)


def solve(N, K, td):
	max_t = [0] * (N + 1)
	for i in range(N):
		if max_t[td[i][0]] < td[i][1]:
			(max_t[td[i][0]], td[i][1]) = (td[i][1], max_t[td[i][0]])
	d = [tdi[1] for tdi in td]
	max_t.sort(reverse=True)
	d.sort(reverse=True)
	c_sum_max_t = [0]
	for i in range(N + 1):
		c_sum_max_t.append(c_sum_max_t[-1] + max_t[i])
	c_sum_d = [0]
	for i in range(N):
		c_sum_d.append(c_sum_d[-1] + d[i])
	ans = 0
	kind = len([i for i in max_t if i > 0])
	for i in range(1, min(kind + 1, K + 1)):
		ans = max(c_sum_max_t[i] + c_sum_d[K - i] + i ** 2, ans)
	print(ans)

def __starting_point():
	(N, K) = list(map(int, input().split()))
	td = [[int(i) for i in input().split()] for _ in range(N)]
	solve(N, K, td)
__starting_point()


from collections import deque as dq
(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: x[1], reverse=True)
ls = set()
dl = dq()
ans = 0
for i in range(K):
	ans += td[i][1]
	if not td[i][0] in ls:
		ls.add(td[i][0])
	else:
		dl.append(td[i][1])
ans = ans + len(ls) ** 2
res = ans
for i in range(K, N):
	if not dl:
		break
	if td[i][0] in ls:
		continue
	ans -= dl[-1]
	ans -= len(ls) * len(ls)
	ls.add(td[i][0])
	ans += len(ls) * len(ls)
	ans += td[i][1]
	del dl[-1]
	res = max(res, ans)
print(res)


(n, k) = map(int, input().split())
from operator import itemgetter as it
l = sorted([list(map(int, input().split())) for i in range(n)], reverse=1, key=it(1))
from collections import defaultdict
c = defaultdict(int)
from heapq import heapify, heappop, heappush
now = []
S = 0
kind = 0
for i in range(k):
	(a, s) = l[i]
	S += s
	c[a] += 1
	if c[a] > 1:
		heappush(now, (s, a))
	kind += c[a] == 1
ans = S + kind ** 2
for i in range(k, n):
	if not now:
		break
	(x, y) = l[i]
	if c[x]:
		continue
	(s, a) = heappop(now)
	c[x] += 1
	kind += 1
	S += y - s
	ans = max(ans, S + kind ** 2)
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
s = [tuple(map(int, input().split())) for _ in range(N)]
s.sort(key=lambda x: -x[1])
table = [(-1, -1)] * (N + 1)
c = 0
for i in range(N):
	if table[s[i][0]] == (-1, -1):
		table[s[i][0]] = (i, s[i][1])
		c += 1
table.sort(key=lambda x: -x[1])
res = [0] * (min(c, M) + 1)
vis = set()
p = M
for i in range(M):
	res[0] += s[i][1]
for x in range(1, min(c, M) + 1):
	res[x] = res[x - 1] + pow(x, 2) - pow(x - 1, 2)
	if table[x - 1][0] >= M:
		res[x] += table[x - 1][1]
		p -= 1
		while p in vis:
			p -= 1
		res[x] -= s[p][1]
	vis.add(table[x - 1][0])
print(max(res))


import sys
from itertools import accumulate
(N, K) = map(int, input().split())
dt = [tuple(map(int, sys.stdin.readline().split()))[::-1] for _ in range(N)]
dt.sort()
ans = sum([d for (d, t) in dt[N - K:]])
repet = []
seen = set()
for _ in range(K):
	(d, t) = dt.pop()
	if t not in seen:
		seen.add(t)
	else:
		repet.append(d)
sp = len(seen)
repet.append(0)
uniq = [0]
for _ in range(N - K):
	(d, t) = dt.pop()
	if t not in seen:
		uniq.append(d)
		seen.add(t)
repet = list(accumulate(repet[::-1]))
uniq = list(accumulate(uniq))
print(ans + max([(sp + i) ** 2 - r + u for (i, (r, u)) in enumerate(zip(repet, uniq))]))


import sys
input = sys.stdin.readline
(N, K) = list(map(int, input().split()))
nums = [[] for i in range(N)]
for i in range(N):
	(t, d) = list(map(int, input().split()))
	t -= 1
	nums[t].append(d)
maxs = []
rest = []
for i in range(N):
	if len(nums[i]) == 0:
		continue
	nums[i].sort(reverse=True)
	maxs.append(nums[i][0])
	for n in nums[i][1:]:
		rest.append(n)
maxs.sort(reverse=True)
rest.sort(reverse=True)
if len(maxs) > K:
	maxs = maxs[:K]
other = []
idx = 0
while len(maxs) + len(other) < K:
	other.append(rest[idx])
	idx += 1
rest = rest[idx:]
types = len(maxs)
for (i, r) in enumerate(rest):
	diff = types * types - pow(types - 1, 2)
	if diff < r - maxs[len(maxs) - 1 - i]:
		maxs[len(maxs) - 1 - i] = r
		types -= 1
	else:
		break
ans = types * types
for num in maxs:
	ans += num
for num in other:
	ans += num
print(ans)


(n, k) = list(map(int, input().split()))
td = []
for _ in range(n):
	td.append(list(map(int, input().split())))
td.sort(key=lambda x: x[1], reverse=True)
td_core = []
td_sel = []
td_sub = []
cat = [0] * (n + 1)
for i in range(n):
	if i < k and cat[td[i][0]] == 0:
		td_core.append(td[i])
		cat[td[i][0]] = 1
	elif i < k:
		td_sel.append(td[i])
	elif cat[td[i][0]] == 0:
		td_sub.append(td[i])
		cat[td[i][0]] = 1
kiso = sum([x[1] for x in td_core]) + sum([x[1] for x in td_sel])
bns = len(td_core)
ans = kiso + bns ** 2
td_sel.sort(key=lambda x: x[1])
for i in range(min(len(td_sel), len(td_sub))):
	kiso -= td_sel[i][1]
	kiso += td_sub[i][1]
	bns += 1
	ans = max(ans, kiso + bns ** 2)
print(ans)


import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline
dd = defaultdict(list)
(N, K) = list(map(int, readline().split()))
for i in range(N):
	(t, d) = list(map(int, readline().split()))
	heapq.heappush(dd[t], d * -1)
dd = list(dd.values())
dd.sort()
ans = 0
fix = 0
var = []
len_var = 0
sum_var = 0
tmp_max = 0
for i in range(min(K, len(dd))):
	fix += heapq.heappop(dd[i]) * -1
	for _ in range(len(dd[i])):
		tmp = heapq.heappop(dd[i]) * -1
		heapq.heappush(var, tmp)
		len_var += 1
		sum_var += tmp
	while len_var > K - (i + 1) and len_var > 0:
		del_var = heapq.heappop(var)
		len_var -= 1
		sum_var -= del_var
	if len_var == K - (i + 1):
		ans = max(ans, fix + sum_var + (i + 1) ** 2)
print(ans)


import heapq
(N, K) = map(int, input().split())
td = [list(map(int, input().split())) for i in range(N)]
td.sort(key=lambda x: -x[1])
sumn = [[] for i in range(N)]
for i in range(N):
	heapq.heapify(sumn[i])
ans = 0
kind = {}
for (t, d) in td[:K]:
	if t not in kind:
		kind[t] = 1
	else:
		kind[t] += 1
	heapq.heappush(sumn[t - 1], d)
kinds = len(kind)
ans = sum((sum(i) for i in sumn))
ans1 = ans + kinds ** 2
rem = td[K:]
nex = 0
candel = []
heapq.heapify(candel)
for (k, v) in kind.items():
	for i in range(v - 1):
		heapq.heappush(candel, heapq.heappop(sumn[k - 1]))
if candel:
	qd = heapq.heappop(candel)
	while K + nex < N:
		if td[K + nex][0] not in kind:
			kind[td[K + nex][0]] = 1
			kinds += 1
			ans = ans - qd + td[K + nex][1]
			ans1 = max(ans1, ans + kinds ** 2)
			nex += 1
			if candel:
				qd = heapq.heappop(candel)
			else:
				break
		else:
			nex += 1
print(ans1)


import sys
from collections import defaultdict
(n, k) = map(int, input().split())
sushi = []
for line in sys.stdin.readlines():
	(t, d) = map(int, line.split())
	sushi.append((d, t))
sushi.sort(reverse=True)
deli = 0
cnt = defaultdict(lambda : 0)
using = sushi[:k]
for (d, t) in sushi[:k]:
	deli += d
	cnt[t] += 1
types = len(cnt)
ans = deli + types ** 2
for (d, t) in sushi[k:]:
	if cnt[t] > 0:
		continue
	(d2, t2) = (None, None)
	while using:
		(d2, t2) = using.pop()
		if cnt[t2] > 1:
			break
	else:
		break
	cnt[t2] -= 1
	cnt[t] += 1
	types += 1
	deli += d - d2
	ans = max(ans, deli + types ** 2)
print(ans)