from itertools import accumulate

N,K = list(map(int,input().split()))

td = [tuple(map(int,input().split())) for i in range(N)]



td = [(x[0]-1,x[1]) for x in td]

td.sort(key=lambda x:-x[1])



t = [-1]*N

for i in range(N):

    t[td[i][0]] = 0

tdK = td[:K]

for i in range(K):

    t[tdK[i][0]] = 1



t_used = [i for i in range(N) if t[i]==1]

t_not_used = [i for i in range(N) if t[i]==0]



d_top = [0]*N

d_top_candi = [0]*N

d_rest = []

d_candi = []



for i in range(K):

    if d_top[td[i][0]] == 0:

        d_top[td[i][0]] = td[i][1]

    else:

        d_rest.append(td[i][1])

for i in range(K,N):

    if t[td[i][0]] == 0:

        if d_top_candi[td[i][0]] == 0:

            d_top_candi[td[i][0]] = 1

            d_candi.append(td[i][1])

l = len(t_used)

s = sum(d_top)

d_rest.sort()

d_candi.sort(key=lambda x:-x)



d_rest_cum = list(accumulate(d_rest))

d_candi_cum = list(accumulate(d_candi))



if len(d_rest) == 0:

    print((l**2 + s))

else:

    s += d_rest_cum[-1]

    ans = l**2 + s

    for k in range(min(len(d_rest),len(d_candi))):

        ans = max((l+k+1)**2 + s + d_candi_cum[k] - d_rest_cum[k],ans)



    print(ans)
N,K = list(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 itertools import accumulate

N, K = list(map(int, input().split()))
td = [tuple(map(int, input().split())) for i in range(N)]
td = [(x[0] - 1, x[1]) for x in td]
td.sort(key=lambda x: -x[1])
t = [-1] * N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[:K]
for i in range(K):
    t[tdK[i][0]] = 1
t_used = [i for i in range(N) if t[i] == 1]
t_not_used = [i for i in range(N) if t[i] == 0]
d_top = [0] * N
d_top_candi = [0] * N
d_rest = []
d_candi = []
for i in range(K):
    if d_top[td[i][0]] == 0:
        d_top[td[i][0]] = td[i][1]
    else:
        d_rest.append(td[i][1])
for i in range(K, N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
s = sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x: -x)
d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))
if len(d_rest) == 0:
    print((l**2 + s))
else:
    s += d_rest_cum[-1]
    ans = l**2 + s
    for k in range(min(len(d_rest), len(d_candi))):
        ans = max((l + k + 1) ** 2 + s + d_candi_cum[k] - d_rest_cum[k], ans)
    print(ans)

N, K = list(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 itertools import accumulate - -td = [tuple(map(int, input().split())) for i in range(N)] -td = [(x[0] - 1, x[1]) for x in td] +td = [list(map(int, input().split())) for _ in range(N)] -t = [-1] * N -for i in range(N): -    t[td[i][0]] = 0 -tdK = td[:K] +l, r = td[:K], td[K:] +used_l = [0] * N -    t[tdK[i][0]] = 1 -t_used = [i for i in range(N) if t[i] == 1] -t_not_used = [i for i in range(N) if t[i] == 0] -d_top = [0] * N -d_top_candi = [0] * N -d_rest = [] -d_candi = [] +    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 -    if d_top[td[i][0]] == 0: -        d_top[td[i][0]] = td[i][1] -    else: -        d_rest.append(td[i][1]) -for i in range(K, N): -    if t[td[i][0]] == 0: -        if d_top_candi[td[i][0]] == 0: -            d_top_candi[td[i][0]] = 1 -            d_candi.append(td[i][1]) -l = len(t_used) -s = sum(d_top) -d_rest.sort() -d_candi.sort(key=lambda x: -x) -d_rest_cum = list(accumulate(d_rest)) -d_candi_cum = list(accumulate(d_candi)) -if len(d_rest) == 0: -    print((l**2 + s)) -else: -    s += d_rest_cum[-1] -    ans = l**2 + s -    for k in range(min(len(d_rest), len(d_candi))): -        ans = max((l + k + 1) ** 2 + s + d_candi_cum[k] - d_rest_cum[k], ans) -    print(ans) +    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)