import heapq as hq

from collections import deque

from copy import deepcopy

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

Sushi = [None for _ in range(N)]

TotalType = set()

for _ in range(N):

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

    Sushi[_] = [d, t]

Sushi.sort(reverse = True)



ChosenType = set()

Double = []

hq.heapify(Double)

BasePoint = 0

for goodsushi in Sushi[:K]:

    BasePoint += goodsushi[0]

    if goodsushi[1] in ChosenType:

        hq.heappush(Double, goodsushi)

    else: ChosenType |= {goodsushi[1]}



NotChosen = deque(deepcopy(Sushi[K:]))

MaxHappiness = BasePoint + len(ChosenType)**2

while Double and NotChosen:

    TrushPoint, TrushType = hq.heappop(Double)

    BasePoint -= TrushPoint

    while NotChosen:

        addPoint, addType = NotChosen.popleft()

        if addType not in ChosenType:

            BasePoint += addPoint

            ChosenType |= {addType}

            break

    MaxHappiness = max(MaxHappiness, BasePoint + len(ChosenType)**2)

print(MaxHappiness)
import sys



def solve():

    input = sys.stdin.readline

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

    S = []

    for _ in range(N):

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

        S.append((d, t))

    S.sort(reverse = True)

    upperKCount = 0

    appeared = set()

    maxPoint = 0

    for i in range(K):

        maxPoint += S[i][0]

        if S[i][1] not in appeared:

            upperKCount += 1

            appeared |= {S[i][1]}

    maxPoint += upperKCount ** 2

    appeared = set()



    typeMax = []

    typeNum = 0

    typeLower = []

    others = 0

    for d, t in S:

        if t in appeared: 

            typeLower.append(d)

            others += 1

        else:

            typeMax.append(d)

            typeNum += 1

            appeared |= {t}

    typeMaxSum = [0] * (typeNum + 1)

    typeLowerSum = [0] * (others + 1)

    for i in range(typeNum): typeMaxSum[i+1] = typeMaxSum[i] + typeMax[i]

    for i in range(others): typeLowerSum[i+1] = typeLowerSum[i] + typeLower[i]

    for k in range(upperKCount + 1, min(typeNum, K) + 1):

        maxPoint = max(maxPoint, k ** 2 + typeMaxSum[k] + typeLowerSum[K - k])

    print(maxPoint)

    return 0



if __name__ == "__main__":

    solve()
import heapq as hq
from collections import deque
from copy import deepcopy

N, K = list(map(int, input().split()))
Sushi = [None for _ in range(N)]
TotalType = set()
for _ in range(N):
    t, d = list(map(int, input().split()))
    Sushi[_] = [d, t]
Sushi.sort(reverse=True)
ChosenType = set()
Double = []
hq.heapify(Double)
BasePoint = 0
for goodsushi in Sushi[:K]:
    BasePoint += goodsushi[0]
    if goodsushi[1] in ChosenType:
        hq.heappush(Double, goodsushi)
    else:
        ChosenType |= {goodsushi[1]}
NotChosen = deque(deepcopy(Sushi[K:]))
MaxHappiness = BasePoint + len(ChosenType) ** 2
while Double and NotChosen:
    TrushPoint, TrushType = hq.heappop(Double)
    BasePoint -= TrushPoint
    while NotChosen:
        addPoint, addType = NotChosen.popleft()
        if addType not in ChosenType:
            BasePoint += addPoint
            ChosenType |= {addType}
            break
    MaxHappiness = max(MaxHappiness, BasePoint + len(ChosenType) ** 2)
print(MaxHappiness)

import sys


def solve():
    input = sys.stdin.readline
    N, K = list(map(int, input().split()))
    S = []
    for _ in range(N):
        t, d = list(map(int, input().split()))
        S.append((d, t))
    S.sort(reverse=True)
    upperKCount = 0
    appeared = set()
    maxPoint = 0
    for i in range(K):
        maxPoint += S[i][0]
        if S[i][1] not in appeared:
            upperKCount += 1
            appeared |= {S[i][1]}
    maxPoint += upperKCount**2
    appeared = set()
    typeMax = []
    typeNum = 0
    typeLower = []
    others = 0
    for d, t in S:
        if t in appeared:
            typeLower.append(d)
            others += 1
        else:
            typeMax.append(d)
            typeNum += 1
            appeared |= {t}
    typeMaxSum = [0] * (typeNum + 1)
    typeLowerSum = [0] * (others + 1)
    for i in range(typeNum):
        typeMaxSum[i + 1] = typeMaxSum[i] + typeMax[i]
    for i in range(others):
        typeLowerSum[i + 1] = typeLowerSum[i] + typeLower[i]
    for k in range(upperKCount + 1, min(typeNum, K) + 1):
        maxPoint = max(maxPoint, k**2 + typeMaxSum[k] + typeLowerSum[K - k])
    print(maxPoint)
    return 0


if __name__ == "__main__":
    solve()

-import heapq as hq -from collections import deque -from copy import deepcopy +import sys -N, K = list(map(int, input().split())) -Sushi = [None for _ in range(N)] -TotalType = set() -for _ in range(N): -    t, d = list(map(int, input().split())) -    Sushi[_] = [d, t] -Sushi.sort(reverse=True) -ChosenType = set() -Double = [] -hq.heapify(Double) -BasePoint = 0 -for goodsushi in Sushi[:K]: -    BasePoint += goodsushi[0] -    if goodsushi[1] in ChosenType: -        hq.heappush(Double, goodsushi) -    else: -        ChosenType |= {goodsushi[1]} -NotChosen = deque(deepcopy(Sushi[K:])) -MaxHappiness = BasePoint + len(ChosenType) ** 2 -while Double and NotChosen: -    TrushPoint, TrushType = hq.heappop(Double) -    BasePoint -= TrushPoint -    while NotChosen: -        addPoint, addType = NotChosen.popleft() -        if addType not in ChosenType: -            BasePoint += addPoint -            ChosenType |= {addType} -            break -    MaxHappiness = max(MaxHappiness, BasePoint + len(ChosenType) ** 2) -print(MaxHappiness) + +def solve(): +    input = sys.stdin.readline +    N, K = list(map(int, input().split())) +    S = [] +    for _ in range(N): +        t, d = list(map(int, input().split())) +        S.append((d, t)) +    S.sort(reverse=True) +    upperKCount = 0 +    appeared = set() +    maxPoint = 0 +    for i in range(K): +        maxPoint += S[i][0] +        if S[i][1] not in appeared: +            upperKCount += 1 +            appeared |= {S[i][1]} +    maxPoint += upperKCount**2 +    appeared = set() +    typeMax = [] +    typeNum = 0 +    typeLower = [] +    others = 0 +    for d, t in S: +        if t in appeared: +            typeLower.append(d) +            others += 1 +        else: +            typeMax.append(d) +            typeNum += 1 +            appeared |= {t} +    typeMaxSum = [0] * (typeNum + 1) +    typeLowerSum = [0] * (others + 1) +    for i in range(typeNum): +        typeMaxSum[i + 1] = typeMaxSum[i] + typeMax[i] +    for i in range(others): +        typeLowerSum[i + 1] = typeLowerSum[i] + typeLower[i] +    for k in range(upperKCount + 1, min(typeNum, K) + 1): +        maxPoint = max(maxPoint, k**2 + typeMaxSum[k] + typeLowerSum[K - k]) +    print(maxPoint) +    return 0 + + +if __name__ == "__main__": +    solve()