from heapq import heappush, heappop

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

log = [0]*N

pre = []

ls = []

for i in range(N):

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

  t = t-1

  heappush(ls,(-d,t))

v = 0

n = 0

for i in range(K):

  d, t = heappop(ls)

  d = -d

  log[t] += 1

  v += d

  if log[t]>1:

    heappush(pre,(d,t))

  else:

    n += 1

v += n*n

ans = v

while ls and pre:

  d, t = heappop(ls)

  if log[t]>0:

    continue

  log[t] += 1

  d = -d

  pv = v

  x, y = heappop(pre)

  v -= x

  v += d

  v += 2*n+1

  n += 1

  if ans<v:

    ans = v

print(ans)
from heapq import heappush, heappop

N, K, *L = list(map(int, open(0).read().split()))

ls = []

for t,d in zip(*[iter(L)]*2):

  ls += [(d,t)]

used = []

cnt = {}

hq = []

S = set()

ls.sort(reverse=True)

m = 0

for i in range(K):

  d,t = ls[i]

  cnt[t] = cnt.get(t,0)+1

  m += d

  if cnt[t]>1:

    heappush(used,(d,t))

  S.add(t)

m += len(S)**2

for i in range(K,N):

  d,t = ls[i]

  if t not in S:

    heappush(hq,(-d,t))

ans = m

while used:

  d,t = heappop(used)

  while hq:

    if hq[0][1] not in S:

      break

    heappop(hq)

  else:

    break

  m -= d

  n,s = heappop(hq)

  m += -n+2*len(S)+1

  ans = max(ans,m)

  S.add(s)

print(ans)
from heapq import heappush, heappop

N, K = list(map(int, input().split()))
log = [0] * N
pre = []
ls = []
for i in range(N):
    t, d = list(map(int, input().split()))
    t = t - 1
    heappush(ls, (-d, t))
v = 0
n = 0
for i in range(K):
    d, t = heappop(ls)
    d = -d
    log[t] += 1
    v += d
    if log[t] > 1:
        heappush(pre, (d, t))
    else:
        n += 1
v += n * n
ans = v
while ls and pre:
    d, t = heappop(ls)
    if log[t] > 0:
        continue
    log[t] += 1
    d = -d
    pv = v
    x, y = heappop(pre)
    v -= x
    v += d
    v += 2 * n + 1
    n += 1
    if ans < v:
        ans = v
print(ans)

from heapq import heappush, heappop

N, K, *L = list(map(int, open(0).read().split()))
ls = []
for t, d in zip(*[iter(L)] * 2):
    ls += [(d, t)]
used = []
cnt = {}
hq = []
S = set()
ls.sort(reverse=True)
m = 0
for i in range(K):
    d, t = ls[i]
    cnt[t] = cnt.get(t, 0) + 1
    m += d
    if cnt[t] > 1:
        heappush(used, (d, t))
    S.add(t)
m += len(S) ** 2
for i in range(K, N):
    d, t = ls[i]
    if t not in S:
        heappush(hq, (-d, t))
ans = m
while used:
    d, t = heappop(used)
    while hq:
        if hq[0][1] not in S:
            break
        heappop(hq)
    else:
        break
    m -= d
    n, s = heappop(hq)
    m += -n + 2 * len(S) + 1
    ans = max(ans, m)
    S.add(s)
print(ans)

-N, K = list(map(int, input().split())) -log = [0] * N -pre = [] +N, K, *L = list(map(int, open(0).read().split())) -for i in range(N): -    t, d = list(map(int, input().split())) -    t = t - 1 -    heappush(ls, (-d, t)) -v = 0 -n = 0 +for t, d in zip(*[iter(L)] * 2): +    ls += [(d, t)] +used = [] +cnt = {} +hq = [] +S = set() +ls.sort(reverse=True) +m = 0 -    d, t = heappop(ls) -    d = -d -    log[t] += 1 -    v += d -    if log[t] > 1: -        heappush(pre, (d, t)) +    d, t = ls[i] +    cnt[t] = cnt.get(t, 0) + 1 +    m += d +    if cnt[t] > 1: +        heappush(used, (d, t)) +    S.add(t) +m += len(S) ** 2 +for i in range(K, N): +    d, t = ls[i] +    if t not in S: +        heappush(hq, (-d, t)) +ans = m +while used: +    d, t = heappop(used) +    while hq: +        if hq[0][1] not in S: +            break +        heappop(hq) -        n += 1 -v += n * n -ans = v -while ls and pre: -    d, t = heappop(ls) -    if log[t] > 0: -        continue -    log[t] += 1 -    d = -d -    pv = v -    x, y = heappop(pre) -    v -= x -    v += d -    v += 2 * n + 1 -    n += 1 -    if ans < v: -        ans = v +        break +    m -= d +    n, s = heappop(hq) +    m += -n + 2 * len(S) + 1 +    ans = max(ans, m) +    S.add(s)