CodeEff/ECCO huggingface dataset:
# Original solution
import itertools
import operator

N, K = list(map(int, input().split()))
sushi = [tuple([i] + [int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = []
choosen_kind = set()
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen.append(x)
        choosen_kind.add(t)
        del left[i]

choosen.sort(key=operator.itemgetter(2), reverse=True)
choosen = choosen[:K]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

tl = list(itertools.islice(list(left.values()), K))
fixed = tl[:K - len(choosen)]
cands = tl[K - len(choosen):]
base += sum(d for _,_,d in fixed)

score = base + kinds**2

if cands:
    comp = []
    while cands and cands[0][2] > choosen[-1][2]:
        base_n = base
        base_n -= choosen[-1][2]
        base_n += cands[0][2]
        kinds_n = kinds - 1
        
        score_n = base_n + kinds_n**2
        if score_n > score:
            choosen = choosen[:-1]
            fixed += cands[0]
            cands = cands[1:]
            base, kinds, score = base_n, kinds_n, score_n
        else:
            break
print(score)

# Optimized solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import islice
import operator

N, K = list(map(int, input().split()))
sushi = [tuple([i] + [int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = [None] * N
choosen_kind = set()
ci = 0
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen[ci] = x
        ci += 1
        choosen_kind.add(t)
        del left[i]

choosen = choosen[:min(ci, K)]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

cands = islice(list(left.values()), K)
fixed = islice(cands, K - len(choosen))
base += sum(d for _,_,d in fixed)

score = base + kinds**2

for cand in cands:
    if cand[2] <= choosen[-1][2]:
        break

    base_n = base
    base_n -= choosen[-1][2]
    base_n += cand[2]
    kinds_n = kinds - 1
    
    score_n = base_n + kinds_n**2
    if score_n > score:
        choosen.pop()
        base, kinds, score = base_n, kinds_n, score_n
    else:
        break

print(score)
# Original solution
def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)

selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
print(maxscore)

# Optimized solution
def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)
'''
selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
'''
kindset = set([])
score = 0
extras = []
for item in sushi[:k]:
    if item[0] in kindset:
        extras.append(item[1])
    else:
        kindset.add(item[0])
    score += item[1]
score += len(kindset)**2
maxscore = score
for item in sushi[k:]:
    if not  extras:
        break
    if item[0] in kindset:
        continue
    score += (item[1] - extras.pop()) + 2*len(kindset) + 1
    kindset.add(item[0])
    #print(score)
    if score > maxscore:
        maxscore = score


print(maxscore)
# Original solution
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)

# Optimized solution
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)
# Original solution
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)

# Optimized solution
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 = [0]*(N+1)
hq = []
S = set()
ls.sort(reverse=True)
m = 0
for i in range(K):
  d,t = ls[i]
  cnt[t] += 1
  m += d
  if cnt[t]>1:
    used.append(d)
  S.add(t)
used.sort(reverse=True)
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 = used.pop()
  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.append(m)
  S.add(s)
print((max(ans)))
# Original solution
from collections import defaultdict
from heapq import heappush, heappop
N,K,*L = list(map(int, open(0).read().split()))
dic = defaultdict(list)
ls = []
for i,(t,d) in enumerate(zip(*[iter(L)]*2)):
  dic[t].append(d)
  heappush(ls,(-d,t))
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
  d,t = heappop(ls)
  ans -= d
  if t not in S:
    num += 1
    S.add(t)
  else:
    heappush(pre,-d)

ans += num*num
if pre==[]:
  print(ans)
  exit()
m = ans
for i in range(N-K):
  d,t = heappop(ls)
  if t in S:
    continue
  S.add(t)
  m -= heappop(pre)
  m += -d+2*num+1
  num += 1
  ans = max(ans,m)
  if pre==[]:
    break
print(ans)

# Optimized solution
N,K,*L = list(map(int, open(0).read().split()))
ls = []
for i,(t,d) in enumerate(zip(*[iter(L)]*2)):
  ls.append((d,t))
ls.sort()
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
  d,t = ls.pop()
  ans += d
  if t not in S:
    num += 1
    S.add(t)
  else:
    pre.append(d)
pre.sort(reverse=True)
ans += num*num
if pre==[]:
  print(ans)
  exit()
m = ans
for i in range(N-K):
  d,t = ls.pop()
  if t in S:
    continue
  S.add(t)
  m -=pre.pop()
  m += d+2*num+1
  num += 1
  ans = max(ans,m)
  if pre==[]:
    break
print(ans)
# Original solution
from operator import itemgetter
from collections import Counter
import heapq

N, K = [int(v) for v in input().split()]
sushi = [tuple(int(v) for v in input().split()) for i in range(N)]

sushi = sorted(sushi, key=itemgetter(1), reverse=True)

ate_list = sushi[:K]

kind_counter = Counter([s[0] for s in ate_list])
kind_cnt = len(list(kind_counter))

kind_cnt_seq = kind_cnt ** 2
max_pt = sum([s[1] for s in ate_list]) + kind_cnt_seq

if K >= N:
    print(max_pt)
    exit()

# print(ate_list)

waiting_sushi = []
wait_kind = []
for s in sushi[K:]:
    if kind_counter[s[0]]:  # すでに食べてる種類
        continue

    if not s[0] in wait_kind:
        waiting_sushi.append(s)
        wait_kind.append(s[0])

# 食べた種類を増やしていくフェーズ
idx = K - 1

# print(waiting_sushi)

curr_pt = max_pt
for s in waiting_sushi:
    target = None
    for i in range(idx, -1, -1):
        # 1個しかないものは交換しない
        if kind_counter[ate_list[i][0]] > 1:
            target = ate_list[i]
            idx = i
            break

    if not target:
        break

    # 入れ替えして比較
    n_kind_cnt_seq = ((kind_cnt + 1) ** 2)
    curr_pt = curr_pt - target[1] + s[1] + n_kind_cnt_seq - kind_cnt_seq
    kind_cnt_seq = n_kind_cnt_seq

    max_pt = max(curr_pt, max_pt)
    kind_counter[target[0]] -= 1

    kind_cnt += 1
    idx -= 1

# print(kind_cnt)
print(max_pt)


# Optimized solution
from operator import itemgetter
from collections import Counter

N, K = [int(v) for v in input().split()]
sushi = [tuple(int(v) for v in input().split()) for i in range(N)]

sushi = sorted(sushi, key=itemgetter(1), reverse=True)

#
# kind_counter = Counter([s[0] for s in ate_list])
# kind_cnt = len(list(kind_counter))

##
# すでにでてきたかどうかがわかれば良いので Counter を使う必要はない
# (数える必要ない)
##

kind = set()
can_converts = []  # 変更しても良いよリスト
max_pt = 0

for i in range(K):
    if sushi[i][0] in kind:
        can_converts.append(sushi[i])
    else:
        kind.add(sushi[i][0])
    max_pt += sushi[i][1]
max_pt += len(kind) ** 2

# 食べた種類を増やしていくフェーズ
curr_pt = max_pt

for s in sushi[K:]:
    if not can_converts: break
    if s[0] not in kind:
        target = can_converts.pop(-1)
        curr_pt = curr_pt - target[1] + s[1] - len(kind) ** 2 + (len(kind) + 1) ** 2
        max_pt = max(max_pt,curr_pt)

        kind.add(s[0])

print(max_pt)

# kind_cnt_seq = kind_cnt ** 2
# max_pt = sum([s[1] for s in ate_list]) + kind_cnt_seq
#
# if K >= N:
#     print(max_pt)
#     exit()
#
# waiting_sushi = []
# wait_kind = []
# for s in sushi[K:]:
#     if kind_counter[s[0]]:  # すでに食べてる種類
#         continue
#
#     if not s[0] in wait_kind:
#         waiting_sushi.append(s)
#         wait_kind.append(s[0])
#
# # 食べた種類を増やしていくフェーズ
# idx = K - 1
# curr_pt = max_pt
# for s in waiting_sushi:
#     target = None
#     for i in range(idx, -1, -1):
#         # 1個しかないものは交換しない
#         if kind_counter[ate_list[i][0]] > 1:
#             target = ate_list[i]
#             idx = i
#             break
#
#     if not target:
#         break
# Original solution
import sys
import heapq as h

input=sys.stdin.readline

N,K=list(map(int,input().split()))
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=list(map(int,input().split()))
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
need=[]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if sushi[i] in need:
            extra.append(sushi[i][0])
        else:
            need.append(sushi[i])
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)

# Optimized solution
import sys
import heapq as h

input=sys.stdin.readline

N,K=list(map(int,input().split()))
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=list(map(int,input().split()))
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
flag=[0 for i in range(0,N+1)]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if flag[sushi[i][1]]==1:
            extra.append(sushi[i][0])
        else:
            flag[sushi[i][1]]=1
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)
# Original solution
n, k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

ab_s = sorted(ab, key=lambda x: x[1])
ab_r = list(reversed(ab_s))

t = [x[0] for x in ab_r]
d = [x[1] for x in ab_r]        

t_set = len(set(t[:k]))
d_sum = sum(d[:k])

res = [t_set**2 + d_sum]

from collections import Counter
t_cou = Counter(t[:k])

dp =[0]*(n+1)
j_old = k-1

for i in t_cou:
    dp[i] = t_cou[i]

for i in range(k,n):
    t_new = ab_r[i][0]
    if dp[t_new] ==0:
        for j in range(j_old,-1,-1):
            t_old = ab_r[j][0]
            if dp[t_old] <=1:
                pass
            else:
                dp[t_new] =1
                dp[t_old] -=1
                t_set +=1
                d_sum = d_sum - ab_r[j][1] + ab_r[i][1]
                res.append(t_set**2 + d_sum)
                j_old = j-1
                break
            j_old = -1

print((max(res)))

# Optimized solution
n, k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

ab_s = sorted(ab, key=lambda x: x[1])
ab_r = list(reversed(ab_s))

t = [x[0] for x in ab_r]
d = [x[1] for x in ab_r]        

t_set = len(set(t[:k]))
d_sum = sum(d[:k])

res = [t_set**2 + d_sum]

from collections import Counter
t_cou = Counter(t[:k])

dp =[0]*(n+1)
j_old = k-1

for i in t_cou:
    dp[i] = t_cou[i]

for i in range(k,n):
    t_new = ab_r[i][0]
    if dp[t_new] ==0:
        for j in range(j_old,-1,-1):
            t_old = ab_r[j][0]
            if dp[t_old] <=1:
                pass
            else:
                dp[t_new] =1
                dp[t_old] -=1
                t_set +=1
                d_sum = d_sum - ab_r[j][1] + ab_r[i][1]
                res.append(t_set**2 + d_sum)
                j_old = j-1
                break
            j_old = 0

print((max(res)))
# Original solution
N,K = list(map(int,input().split()))

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

TDlist.sort(key = lambda x: x[1],reverse=True)
kinds = []
seconds = []
answer = 0

for x in TDlist[:K]:
    if not x[0] in kinds:
        kinds.append(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer
max_score = answer

for x in TDlist[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.append(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    max_score = max(score,answer)
    

answer = max(answer,max_score)

print(answer)

# Optimized solution
N,K = list(map(int,input().split()))
TDlist = []

for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

TDlist= sorted(TDlist, key = lambda x: x[1],reverse=True)
kinds = set()
seconds = []
answer = 0

for x in TDlist[:K]:
    if not x[0] in kinds:
        kinds.add(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer

for x in TDlist[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.add(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    answer = max(score,answer)

print(answer)
# Original solution
n,k=list(map(int,input().split()))
inf=10**18
sushi=[[-inf] for _ in range(n)]
for i in range(n):
  t,d=list(map(int,input().split()))
  sushi[t-1].append(d)
for i in range(n):
  sushi[i].sort(reverse=True)
sushi.sort(key=lambda x:x[0],reverse=True)
q=[]
res=0
for i in range(k):
  res+=sushi[i][0]
  for j in sushi[i][1:]:
    q.append(j)
q.sort()
cur=res
res+=k**2
for var in range(1,k)[::-1]:
  a=q.pop()
  b=sushi[var][0]
  cur+=a-b
  res=max(res,cur+var**2)
print(res)

# Optimized solution
n,k=list(map(int,input().split()))
INF=10**18
sushi=[[-INF] for _ in range(n)]
for _ in range(n):
  t,d=list(map(int,input().split()))
  sushi[t-1].append(d)
for i in range(n):
  sushi[i].sort(reverse=True)
sushi.sort(key=lambda x:x[0],reverse=True)
q=[]
res=0
for i in range(k):
  res+=sushi[i][0]
  for j in sushi[i][1:]:
    q.append(j)
q.sort()
cur=res
res+=k**2
for var in range(1,k)[::-1]:
  a=q.pop()
  b=sushi[var][0]
  cur+=a-b
  res=max(res,cur+var**2)
print(res)
# Original solution
N,K=list(map(int,input().split()))
t=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    t[i],d[i]=list(map(int,input().split()))
D=dict()
for i in range(N):
    if not(t[i] in D):
        D[t[i]]=[]
    D[t[i]].append((d[i],i))
E=[0 for i in range(N)]
for key in D:
    D[key].sort(reverse=True)
    E[D[key][0][1]]=1
A=[]
B=[]
for i in range(N):
    if E[i]==1:
        A.append(d[i])
    else:
        B.append(d[i])
A.sort(reverse=True)
B.sort(reverse=True)
X=len(A)
Y=len(B)
S=[0 for i in range(X+1)]
T=[0 for i in range(Y+1)]
for i in range(X):
    S[i+1]=A[i]+S[i]
for i in range(Y):
    T[i+1]=B[i]+T[i]
L=[]
for i in range(1,K+1):
    if i<=X and K-i<=Y:
        L.append(S[i]+T[K-i]+i*i)
print((max(L)))

# Optimized solution
N,K=list(map(int,input().split()))
sushi=[]
for i in range(N):
    t,d=list(map(int,input().split()))
    sushi.append((t,d))
sushi.sort(key=lambda x:(x[0],-x[1]))
#print(sushi)
X=[sushi[0][1]]
Y=[]
for i in range(1,N):
    if sushi[i-1][0]==sushi[i][0]:
        Y.append(sushi[i][1])
    else:
        X.append(sushi[i][1])
X.sort(reverse=True)
Y.sort(reverse=True)
SX=[0]
SY=[0]
for i in X:
    SX.append(SX[-1]+i)
for i in Y:
    SY.append(SY[-1]+i)
ans=0
#print(X)
#print(Y)
#1<=x<len(X)
#K-len(Y)<=x<=
for x in range(max(1,K-len(Y)),min(len(SX),K+1)):
    ans=max(SX[x]+SY[K-x]+x*x,ans)
print(ans)
# Original solution
def solve():
    from collections import namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Sushi = namedtuple('Sushi', 'taste kind')

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

    e = []
    for _ in range(n):
        t, d = list(map(int, input().split()))
        e.append(Sushi(taste=d, kind=t - 1))

    e.sort(key=attrgetter('taste'), reverse=True)

    b = e[:k]  # 美味しさ降順k個

    ret = 0
    used = [False] * n  # 選択されている種類
    h = []  # 選択から外す候補
    x = 0  # 暫定選択の種類数
    for s in b:
        if used[s.kind]:
            heappush(h, s)
        else:
            used[s.kind] = True
            x += 1
        ret += s.taste

    ret += pow(x, 2)  # 種類ボーナス

    t = ret
    r = iter(e[k:])  # 交換で入れる候補
    while h:
        rem = heappop(h)  # 選択から外す
        t -= rem.taste

        for s in r:
            if used[s.kind]:
                continue
            used[s.kind] = True
            t += s.taste + x * 2 + 1
            x += 1
            ret = max(ret, t)
            break
        else:
            break

    return ret


if __name__ == '__main__':
    print((solve()))


# Optimized solution
def solve():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Sushi = namedtuple('Sushi', 'taste kind')

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

    e = []
    for _ in range(n):
        t, d = list(map(int, input().split()))
        e.append(Sushi(taste=d, kind=t - 1))

    e.sort(key=attrgetter('taste'), reverse=True)

    ret = 0
    used = [False] * n  # 選択されている種類
    q = deque()  # 選択から外す候補,[high->low]
    x = 0  # 暫定選択の種類数
    for s in e[:k]:  # 美味しさ降順k個
        if used[s.kind]:
            q.append(s)  # 同じ種類の2個目以降のみ交換候補になる
        else:
            used[s.kind] = True
            x += 1
        ret += s.taste
    ret += pow(x, 2)  # 種類ボーナス

    t = ret
    r = iter(e[k:])  # 交換で入れる候補
    while q:
        rem = q.pop()  # 選択から外す
        t -= rem.taste
        for s in r:
            if used[s.kind]:
                continue
            used[s.kind] = True
            t += s.taste + x * 2 + 1
            x += 1
            ret = max(ret, t)
            break
        else:
            break

    return ret


if __name__ == '__main__':
    print((solve()))

# k個持っておいて、下位を交換する