from operator import itemgetter

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

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

td.sort(key=itemgetter(1, 0), reverse=True)

t, d = list(zip(*td))



s = set()

q = []

tmp = 0

now = 0

for i in range(K):

    if t[i] not in s:

        s.add(t[i])

    else:

        q.append(d[i])



    tmp += d[i]

    now += 1

kind = len(s)

sums = [-100000000000]*(kind+1)

sums[kind] = tmp

for i in range(K, N):

    if not q:

        break

    if t[i] not in s:

        s.add(t[i])

        tmp = q.pop()

        kind += 1

        sums.append(sums[kind-1] + d[i] - tmp)

#while q:

#    kind += 1

#    tmp = q.pop()

#    for i in range(now, N):

#        now += 1

#        if t[i] not in s:

#            s.add(t[i])

#            sums.append(sums[kind-1] + d[i] - tmp)

#            break

for i in range(len(sums)):

    sums[i] += i**2

print((max(sums)))



from operator import itemgetter

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

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

td.sort(key=itemgetter(1), reverse=True)

t, d = list(zip(*td))



s = set()

q = []

tmp = 0

now = 0

for i in range(K):

    if t[i] not in s:

        s.add(t[i])

    else:

        q.append(d[i])



    tmp += d[i]

    now += 1

kind = len(s)

sums = [-100000000000]*(kind+1)

sums[kind] = tmp

for i in range(K, N):

    if not q:

        break

    if t[i] not in s:

        s.add(t[i])

        tmp = q.pop()

        kind += 1

        sums.append(sums[kind-1] + d[i] - tmp)

for i in range(len(sums)):

    sums[i] += i**2

print((max(sums)))



from operator import itemgetter

N, K = list(map(int, input().split()))
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = list(zip(*td))
s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])
    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000] * (kind + 1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind - 1] + d[i] - tmp)
# while q:
#    kind += 1
#    tmp = q.pop()
#    for i in range(now, N):
#        now += 1
#        if t[i] not in s:
#            s.add(t[i])
#            sums.append(sums[kind-1] + d[i] - tmp)
#            break
for i in range(len(sums)):
    sums[i] += i**2
print((max(sums)))

from operator import itemgetter

N, K = list(map(int, input().split()))
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1), reverse=True)
t, d = list(zip(*td))
s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])
    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000] * (kind + 1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind - 1] + d[i] - tmp)
for i in range(len(sums)):
    sums[i] += i**2
print((max(sums)))

-td.sort(key=itemgetter(1, 0), reverse=True) +td.sort(key=itemgetter(1), reverse=True) -# while q: -#    kind += 1 -#    tmp = q.pop() -#    for i in range(now, N): -#        now += 1 -#        if t[i] not in s: -#            s.add(t[i]) -#            sums.append(sums[kind-1] + d[i] - tmp) -#            break