# 解説放送



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



e = [None for _ in range(N + 1)] # 種別の美味しさ

t_kinds_count = 0 # 何種類あるか

rest_length = 0 # 各種の2番手以降の個数の総数



tops = [] # 各種の最大美味しさ

c_tops = [0] # 各種の最大美味しさの累積和

rests = [] # 各種の2番手以降

c_rests = [0] # 各種の2番手以降の累積和



for _ in range(N):

    t, d = list(map(int, input().split()))

    if e[t] is None:

        e[t] = []

        t_kinds_count += 1

    e[t].append(d)





for t in range(1, N + 1):

    if e[t] is None:

        continue

    e[t].sort(reverse=True)

    tops.append(e[t][0])

    rests.extend(e[t][1:])



tops.sort(reverse=True)

rests.sort(reverse=True)



s = 0

for tt in tops:

    s += tt

    c_tops.append(s)



s = 0

for rr in rests:

    s += rr

    c_rests.append(s)

    rest_length += 1



ans = 0

for yy in range(1, min(t_kinds_count, K) + 1):

    if 0 <= K - yy <= rest_length:

        ans = max(ans, c_tops[yy] + c_rests[K - yy] + yy * yy)



# print(e)

# print(tops)

# print(c_tops)

# print(rests)

# print(c_rests)

print(ans)

from heapq import heappush, heappop

from operator import itemgetter

import sys



input = sys.stdin.readline



n, k = list(map(int, input().split()))

e = []

for _ in range(n):

    t, d = list(map(int, input().split()))

    t -= 1

    e.append((d, t))



e.sort(key=itemgetter(0), reverse=True)



b = e[:k]  # 暫定選択（おいしさ基礎ポイント降順取得）



used = [False] * n

hq = []



ans = 0  # 暫定選択（おいしさ基礎ポイント降順取得）

tn = 0  # 種類数

for d, t in b:

    if not used[t]:

        used[t] = True

        tn += 1

    else:

        heappush(hq, (d, t))

    ans += d

ans += pow(tn, 2)  # 種類ボーナス



c = e[k:]  # 取得しなかった予備



# print(b)

# print(c)

# print(hq)

# print(used)

s = ans

cur = 0

while hq:

    d, t = heappop(hq)

    s -= d

    changed = False

    while cur < n - k:

        cd, ct = c[cur]

        cur += 1

        if not used[ct]:

            used[ct] = True

            changed = True

            s += cd

            s += tn * 2 + 1

            tn += 1

            if s > ans:

                ans = s

            break

    if not changed:

        break

print(ans)

# 解説放送
N, K = list(map(int, input().split()))
e = [None for _ in range(N + 1)]  # 種別の美味しさ
t_kinds_count = 0  # 何種類あるか
rest_length = 0  # 各種の2番手以降の個数の総数
tops = []  # 各種の最大美味しさ
c_tops = [0]  # 各種の最大美味しさの累積和
rests = []  # 各種の2番手以降
c_rests = [0]  # 各種の2番手以降の累積和
for _ in range(N):
    t, d = list(map(int, input().split()))
    if e[t] is None:
        e[t] = []
        t_kinds_count += 1
    e[t].append(d)
for t in range(1, N + 1):
    if e[t] is None:
        continue
    e[t].sort(reverse=True)
    tops.append(e[t][0])
    rests.extend(e[t][1:])
tops.sort(reverse=True)
rests.sort(reverse=True)
s = 0
for tt in tops:
    s += tt
    c_tops.append(s)
s = 0
for rr in rests:
    s += rr
    c_rests.append(s)
    rest_length += 1
ans = 0
for yy in range(1, min(t_kinds_count, K) + 1):
    if 0 <= K - yy <= rest_length:
        ans = max(ans, c_tops[yy] + c_rests[K - yy] + yy * yy)
# print(e)
# print(tops)
# print(c_tops)
# print(rests)
# print(c_rests)
print(ans)

from heapq import heappush, heappop
from operator import itemgetter
import sys

input = sys.stdin.readline
n, k = list(map(int, input().split()))
e = []
for _ in range(n):
    t, d = list(map(int, input().split()))
    t -= 1
    e.append((d, t))
e.sort(key=itemgetter(0), reverse=True)
b = e[:k]  # 暫定選択（おいしさ基礎ポイント降順取得）
used = [False] * n
hq = []
ans = 0  # 暫定選択（おいしさ基礎ポイント降順取得）
tn = 0  # 種類数
for d, t in b:
    if not used[t]:
        used[t] = True
        tn += 1
    else:
        heappush(hq, (d, t))
    ans += d
ans += pow(tn, 2)  # 種類ボーナス
c = e[k:]  # 取得しなかった予備
# print(b)
# print(c)
# print(hq)
# print(used)
s = ans
cur = 0
while hq:
    d, t = heappop(hq)
    s -= d
    changed = False
    while cur < n - k:
        cd, ct = c[cur]
        cur += 1
        if not used[ct]:
            used[ct] = True
            changed = True
            s += cd
            s += tn * 2 + 1
            tn += 1
            if s > ans:
                ans = s
            break
    if not changed:
        break
print(ans)

-# 解説放送 -N, K = list(map(int, input().split())) -e = [None for _ in range(N + 1)]  # 種別の美味しさ -t_kinds_count = 0  # 何種類あるか -rest_length = 0  # 各種の2番手以降の個数の総数 -tops = []  # 各種の最大美味しさ -c_tops = [0]  # 各種の最大美味しさの累積和 -rests = []  # 各種の2番手以降 -c_rests = [0]  # 各種の2番手以降の累積和 -for _ in range(N): +from heapq import heappush, heappop +from operator import itemgetter +import sys + +input = sys.stdin.readline +n, k = list(map(int, input().split())) +e = [] +for _ in range(n): -    if e[t] is None: -        e[t] = [] -        t_kinds_count += 1 -    e[t].append(d) -for t in range(1, N + 1): -    if e[t] is None: -        continue -    e[t].sort(reverse=True) -    tops.append(e[t][0]) -    rests.extend(e[t][1:]) -tops.sort(reverse=True) -rests.sort(reverse=True) -s = 0 -for tt in tops: -    s += tt -    c_tops.append(s) -s = 0 -for rr in rests: -    s += rr -    c_rests.append(s) -    rest_length += 1 -ans = 0 -for yy in range(1, min(t_kinds_count, K) + 1): -    if 0 <= K - yy <= rest_length: -        ans = max(ans, c_tops[yy] + c_rests[K - yy] + yy * yy) -# print(e) -# print(tops) -# print(c_tops) -# print(rests) -# print(c_rests) +    t -= 1 +    e.append((d, t)) +e.sort(key=itemgetter(0), reverse=True) +b = e[:k]  # 暫定選択（おいしさ基礎ポイント降順取得） +used = [False] * n +hq = [] +ans = 0  # 暫定選択（おいしさ基礎ポイント降順取得） +tn = 0  # 種類数 +for d, t in b: +    if not used[t]: +        used[t] = True +        tn += 1 +    else: +        heappush(hq, (d, t)) +    ans += d +ans += pow(tn, 2)  # 種類ボーナス +c = e[k:]  # 取得しなかった予備 +# print(b) +# print(c) +# print(hq) +# print(used) +s = ans +cur = 0 +while hq: +    d, t = heappop(hq) +    s -= d +    changed = False +    while cur < n - k: +        cd, ct = c[cur] +        cur += 1 +        if not used[ct]: +            used[ct] = True +            changed = True +            s += cd +            s += tn * 2 + 1 +            tn += 1 +            if s > ans: +                ans = s +            break +    if not changed: +        break