from heapq import heappop, heappush

from collections import defaultdict



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

X = [list(map(int, input().split())) for _ in range(N)]



# Step 1: Choose greedy

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

pq = []

chosen = defaultdict(int)

cnt = 0

score = 0

for t, d in X[:K]:

    heappush(pq, (d, t))

    cnt += 1 if chosen[t] == 0 else 0

    chosen[t] += 1

    score += d

ans = score + cnt ** 2



# Step 2: Replace chosen items

idx = K

while pq:

    # Step 2.1

    d_p, t_p = heappop(pq)

    if chosen[t_p] <= 1:

        continue

    chosen[t_p] -= 1

    score -= d_p



    # Step 2.2

    while idx < N and chosen[X[idx][0]] != 0:

        idx += 1



    if idx == N:

        break

        

    cnt += 1

    chosen[X[idx][0]] += 1

    score += X[idx][1]

    ans = max(ans, score + cnt ** 2)

    

print(ans)





from collections import defaultdict

from heapq import heappop, heappush



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

X = [list(map(int, input().split())) for _ in range(N)]



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

pq = []

f_x = 0

ctr = defaultdict(int)

appeared = 0

for _ in range(K):

    t, d = X.pop()

    heappush(pq, (d, t))

    appeared += int(ctr[t] == 0)

    f_x += d

    ctr[t] += 1



res = f_x + appeared ** 2

while pq or X:

    while pq:

        d, t = heappop(pq)

        if ctr[t] > 1:

            ctr[t] -= 1

            f_x -= d

            break



    if not pq:

        break



    while X:

        t_x, d_x = X.pop()

        if ctr[t_x] == 0:

            heappush(pq, (d_x, t_x))

            f_x += d_x

            ctr[t_x] += 1

            appeared += 1

            res = max(res, f_x + appeared ** 2)

            break



print(res)

from heapq import heappop, heappush
from collections import defaultdict

N, K = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N)]
# Step 1: Choose greedy
X.sort(key=lambda x: -x[1])
pq = []
chosen = defaultdict(int)
cnt = 0
score = 0
for t, d in X[:K]:
    heappush(pq, (d, t))
    cnt += 1 if chosen[t] == 0 else 0
    chosen[t] += 1
    score += d
ans = score + cnt**2
# Step 2: Replace chosen items
idx = K
while pq:
    # Step 2.1
    d_p, t_p = heappop(pq)
    if chosen[t_p] <= 1:
        continue
    chosen[t_p] -= 1
    score -= d_p
    # Step 2.2
    while idx < N and chosen[X[idx][0]] != 0:
        idx += 1
    if idx == N:
        break
    cnt += 1
    chosen[X[idx][0]] += 1
    score += X[idx][1]
    ans = max(ans, score + cnt**2)
print(ans)

from collections import defaultdict
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key=lambda x: x[1])
pq = []
f_x = 0
ctr = defaultdict(int)
appeared = 0
for _ in range(K):
    t, d = X.pop()
    heappush(pq, (d, t))
    appeared += int(ctr[t] == 0)
    f_x += d
    ctr[t] += 1
res = f_x + appeared**2
while pq or X:
    while pq:
        d, t = heappop(pq)
        if ctr[t] > 1:
            ctr[t] -= 1
            f_x -= d
            break
    if not pq:
        break
    while X:
        t_x, d_x = X.pop()
        if ctr[t_x] == 0:
            heappush(pq, (d_x, t_x))
            f_x += d_x
            ctr[t_x] += 1
            appeared += 1
            res = max(res, f_x + appeared**2)
            break
print(res)

+from collections import defaultdict -from collections import defaultdict -# Step 1: Choose greedy -X.sort(key=lambda x: -x[1]) +X.sort(key=lambda x: x[1]) -chosen = defaultdict(int) -cnt = 0 -score = 0 -for t, d in X[:K]: +f_x = 0 +ctr = defaultdict(int) +appeared = 0 +for _ in range(K): +    t, d = X.pop() -    cnt += 1 if chosen[t] == 0 else 0 -    chosen[t] += 1 -    score += d -ans = score + cnt**2 -# Step 2: Replace chosen items -idx = K -while pq: -    # Step 2.1 -    d_p, t_p = heappop(pq) -    if chosen[t_p] <= 1: -        continue -    chosen[t_p] -= 1 -    score -= d_p -    # Step 2.2 -    while idx < N and chosen[X[idx][0]] != 0: -        idx += 1 -    if idx == N: +    appeared += int(ctr[t] == 0) +    f_x += d +    ctr[t] += 1 +res = f_x + appeared**2 +while pq or X: +    while pq: +        d, t = heappop(pq) +        if ctr[t] > 1: +            ctr[t] -= 1 +            f_x -= d +            break +    if not pq: -    cnt += 1 -    chosen[X[idx][0]] += 1 -    score += X[idx][1] -    ans = max(ans, score + cnt**2) -print(ans) +    while X: +        t_x, d_x = X.pop() +        if ctr[t_x] == 0: +            heappush(pq, (d_x, t_x)) +            f_x += d_x +            ctr[t_x] += 1 +            appeared += 1 +            res = max(res, f_x + appeared**2) +            break +print(res)