from collections import Counter

N,K = list(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

    else:

        break

print(ans)
N,K = list(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)
from collections import Counter

N, K = list(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
    else:
        break
print(ans)

N, K = list(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)

-from collections import Counter +N, K = list(map(int, input().split())) +TD = [tuple(map(int, input().split())) for i in range(N)] +TD.sort(key=lambda x: x[1]) +import heapq -N, K = list(map(int, input().split())) -src = [tuple(map(int, input().split())) for i in range(N)] -src.sort(key=lambda x: -x[1]) -selected = Counter() +hq = [] +heapq.heapify(hq) +selected = set() -stack = [] -for t, d in src[:K]: +for _ in range(K): +    t, d = TD.pop() +    if t in selected: +        heapq.heappush(hq, d) +    else: +        selected.add(t) -    selected[t] += 1 -    stack.append((t, d)) -for t, d in src[K:]: +while TD: +    t, d = TD.pop() -    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 -    else: +    selected.add(t) +    if len(hq) == 0: +    tmp -= heapq.heappop(hq) +    tmp += d +    tmp += len(selected) * 2 - 1 +    ans = max(ans, tmp)