from heapq import heappop, heappush



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

a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (-x[1], x[0]))



totalTaste = 0

same = []

types = set()

for i in range(nTake):

    type, taste = a[i]

    totalTaste += taste

    if type not in types:

        types.add(type)

    else:

        heappush(same, taste)



rem = []

typesRem = set()

for i in range(nTake, n):

    type, taste = a[i]

    if type not in types and type not in typesRem:

        typesRem.add(type)

        heappush(rem, -taste)



ret = totalTaste + len(types) ** 2

curTotal = totalTaste

add = 1

while same and rem:

    worst = heappop(same)

    best = heappop(rem)

    curTotal = curTotal - worst - best

    ret = max(ret, curTotal + (len(types) + add) ** 2)

    add += 1

print(ret)
n, nTake = list(map(int, input().split()))

a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])



totalTaste = 0

same = []

types = set()

for i in range(nTake):

    type, taste = a[i]

    totalTaste += taste

    if type not in types:

        types.add(type)

    else:

        same.append(taste)



rem = []

typesRem = set()

for i in range(nTake, n):

    type, taste = a[i]

    if type not in types and type not in typesRem:

        typesRem.add(type)

        rem.append(taste)



same.sort()

rem.sort(key=lambda x: -x)

ret = totalTaste + len(types) ** 2

curTotal = totalTaste

for i in range(min(len(same), len(rem))):

    curTotal = curTotal - same[i] + rem[i]

    ret = max(ret, curTotal + (len(types) + i + 1) ** 2)

print(ret)
from heapq import heappop, heappush

n, nTake = list(map(int, input().split()))
a = sorted(
    [tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (-x[1], x[0])
)
totalTaste = 0
same = []
types = set()
for i in range(nTake):
    type, taste = a[i]
    totalTaste += taste
    if type not in types:
        types.add(type)
    else:
        heappush(same, taste)
rem = []
typesRem = set()
for i in range(nTake, n):
    type, taste = a[i]
    if type not in types and type not in typesRem:
        typesRem.add(type)
        heappush(rem, -taste)
ret = totalTaste + len(types) ** 2
curTotal = totalTaste
add = 1
while same and rem:
    worst = heappop(same)
    best = heappop(rem)
    curTotal = curTotal - worst - best
    ret = max(ret, curTotal + (len(types) + add) ** 2)
    add += 1
print(ret)

n, nTake = list(map(int, input().split()))
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])
totalTaste = 0
same = []
types = set()
for i in range(nTake):
    type, taste = a[i]
    totalTaste += taste
    if type not in types:
        types.add(type)
    else:
        same.append(taste)
rem = []
typesRem = set()
for i in range(nTake, n):
    type, taste = a[i]
    if type not in types and type not in typesRem:
        typesRem.add(type)
        rem.append(taste)
same.sort()
rem.sort(key=lambda x: -x)
ret = totalTaste + len(types) ** 2
curTotal = totalTaste
for i in range(min(len(same), len(rem))):
    curTotal = curTotal - same[i] + rem[i]
    ret = max(ret, curTotal + (len(types) + i + 1) ** 2)
print(ret)

-from heapq import heappop, heappush - -a = sorted( -    [tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (-x[1], x[0]) -) +a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1]) -        heappush(same, taste) +        same.append(taste) -        heappush(rem, -taste) +        rem.append(taste) +same.sort() +rem.sort(key=lambda x: -x) -add = 1 -while same and rem: -    worst = heappop(same) -    best = heappop(rem) -    curTotal = curTotal - worst - best -    ret = max(ret, curTotal + (len(types) + add) ** 2) -    add += 1 +for i in range(min(len(same), len(rem))): +    curTotal = curTotal - same[i] + rem[i] +    ret = max(ret, curTotal + (len(types) + i + 1) ** 2)