from operator import itemgetter

from functools import reduce

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

t, d = list(zip(*(list(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)
from heapq import heappush, heappop



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

t, d = (

    list(zip(*(list(map(int, input().split())) for _ in range(N)))) if N else

    ((), ())

)



# おいしさについて貪欲に寿司を食べたときの満足ポイントを求める

# その後、種類ボーナスを1個ずつ増やしたときの満足ポイントをそれぞれ求め、

# それらの最大値を求める

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)

from operator import itemgetter
from functools import reduce

N, K = list(map(int, input().split()))
t, d = list(zip(*(list(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)

from heapq import heappush, heappop

N, K = list(map(int, input().split()))
t, d = (
    list(zip(*(list(map(int, input().split())) for _ in range(N)))) if N else ((), ())
)
# おいしさについて貪欲に寿司を食べたときの満足ポイントを求める
# その後、種類ボーナスを1個ずつ増やしたときの満足ポイントをそれぞれ求め、
# それらの最大値を求める
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)

-from operator import itemgetter -from functools import reduce +from heapq import heappush, heappop -t, d = list(zip(*(list(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]) +t, d = ( +    list(zip(*(list(map(int, input().split())) for _ in range(N)))) if N else ((), ()) +) +# おいしさについて貪欲に寿司を食べたときの満足ポイントを求める +# その後、種類ボーナスを1個ずつ増やしたときの満足ポイントをそれぞれ求め、 +# それらの最大値を求める +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) -        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) +        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