import sys

input = sys.stdin.readline



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

nums = [[] for i in range(N)]

for i in range(N):

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

    t -= 1

    nums[t].append(d)

maxs = []

rest = []

for i in range(N):

    if len(nums[i]) == 0: continue

    nums[i].sort(reverse=True)

    maxs.append(nums[i][0])

    for n in nums[i][1:]:

        rest.append(n)

maxs.sort(reverse=True)

rest.sort(reverse=True)

if len(maxs) > K:

    maxs = maxs[:K]

other = []

idx = 0

while len(maxs)+len(other) < K:

    other.append(rest[idx])

    idx += 1

rest = rest[idx:]



types = len(maxs)

for i,r in enumerate(rest):

    diff = types*types - pow(types-1, 2)

    if diff < r-maxs[len(maxs)-1-i]:

        maxs[len(maxs)-1-i] = r

        types -= 1

    else:

        break

ans = types*types

for num in maxs:

    ans += num

for num in other:

    ans += num

print(ans)

import sys

input = sys.stdin.readline



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

nums = []

for i in range(N):

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

    nums.append((d, t))

nums.sort(reverse=True)

se = set()

a1 = []

a2 = []

rest = []

for i, n in enumerate(nums):

    if i < K:

        if not n[1] in se:

            se.add(n[1])

            a1.append(n)

        else:

            a2.append(n)

    else:

        rest.append(n)

points = 0

for (d, t) in a1: points += d

for (d, t) in a2: points += d

ans = points + pow(len(se), 2)

a2.sort()

idx2 = 0

for i, (d, t) in enumerate(rest):

    if t in se: continue

    if len(a2) <= idx2: break

    points -= a2[idx2][0]

    idx2 += 1

    points += d

    se.add(t)

    ans = max(ans, points+pow(len(se), 2))

print(ans)

import sys

input = sys.stdin.readline
N, K = list(map(int, input().split()))
nums = [[] for i in range(N)]
for i in range(N):
    t, d = list(map(int, input().split()))
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    if len(nums[i]) == 0:
        continue
    nums[i].sort(reverse=True)
    maxs.append(nums[i][0])
    for n in nums[i][1:]:
        rest.append(n)
maxs.sort(reverse=True)
rest.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
other = []
idx = 0
while len(maxs) + len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]
types = len(maxs)
for i, r in enumerate(rest):
    diff = types * types - pow(types - 1, 2)
    if diff < r - maxs[len(maxs) - 1 - i]:
        maxs[len(maxs) - 1 - i] = r
        types -= 1
    else:
        break
ans = types * types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)

import sys

input = sys.stdin.readline
N, K = list(map(int, input().split()))
nums = []
for i in range(N):
    t, d = list(map(int, input().split()))
    nums.append((d, t))
nums.sort(reverse=True)
se = set()
a1 = []
a2 = []
rest = []
for i, n in enumerate(nums):
    if i < K:
        if not n[1] in se:
            se.add(n[1])
            a1.append(n)
        else:
            a2.append(n)
    else:
        rest.append(n)
points = 0
for (d, t) in a1:
    points += d
for (d, t) in a2:
    points += d
ans = points + pow(len(se), 2)
a2.sort()
idx2 = 0
for i, (d, t) in enumerate(rest):
    if t in se:
        continue
    if len(a2) <= idx2:
        break
    points -= a2[idx2][0]
    idx2 += 1
    points += d
    se.add(t)
    ans = max(ans, points + pow(len(se), 2))
print(ans)

-nums = [[] for i in range(N)] +nums = [] -    t -= 1 -    nums[t].append(d) -maxs = [] +    nums.append((d, t)) +nums.sort(reverse=True) +se = set() +a1 = [] +a2 = [] -for i in range(N): -    if len(nums[i]) == 0: +for i, n in enumerate(nums): +    if i < K: +        if not n[1] in se: +            se.add(n[1]) +            a1.append(n) +        else: +            a2.append(n) +    else: +        rest.append(n) +points = 0 +for (d, t) in a1: +    points += d +for (d, t) in a2: +    points += d +ans = points + pow(len(se), 2) +a2.sort() +idx2 = 0 +for i, (d, t) in enumerate(rest): +    if t in se: -    nums[i].sort(reverse=True) -    maxs.append(nums[i][0]) -    for n in nums[i][1:]: -        rest.append(n) -maxs.sort(reverse=True) -rest.sort(reverse=True) -if len(maxs) > K: -    maxs = maxs[:K] -other = [] -idx = 0 -while len(maxs) + len(other) < K: -    other.append(rest[idx]) -    idx += 1 -rest = rest[idx:] -types = len(maxs) -for i, r in enumerate(rest): -    diff = types * types - pow(types - 1, 2) -    if diff < r - maxs[len(maxs) - 1 - i]: -        maxs[len(maxs) - 1 - i] = r -        types -= 1 -    else: +    if len(a2) <= idx2: -ans = types * types -for num in maxs: -    ans += num -for num in other: -    ans += num +    points -= a2[idx2][0] +    idx2 += 1 +    points += d +    se.add(t) +    ans = max(ans, points + pow(len(se), 2))