Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
td=[]
for _ in range(n):
  td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
td_core=[]
td_sel=[]
td_sub=[]
cat=[0]*(n+1)
for i in range(n):
  if i < k and cat[td[i][0]]==0:
    td_core.append(td[i])
    cat[td[i][0]]=1
  elif i < k:
    td_sel.append(td[i])
  elif cat[td[i][0]]==0:
    td_sub.append(td[i])
    cat[td[i][0]]=1
# i >= k and cat[td[i][0]]==1 となるものはすでにtd_core,td_sel,td_sub内ものと種類も被っている上に美味しさも低い
# 後の工程では種類を増やす処理なので、同じ種類のネタは美味しさが最大のもの一つで十分。なので捨てる

# dの大きいじゅんに貪欲にネタを取得したときの満足ポイント
kiso=sum([x[1] for x in td_core])+sum(x[1] for x in td_sel)
bns=len(td_core)
ans=kiso+bns**2
# この状態からネタの種類を増やしていき最大が出てくるか検証
# td_sel内のネタは同一ネタが複数あり、そのネタ内で最大じゃないものが美味しさの大きい順に入っている。
# td_subにはtd_core,tdselにないネタの最大美味しさの寿司が入っている。
td_sel.sort(key=lambda x:x[0])
for i in range(len(td_sel)):
  kiso-=td_sel[i][1]
  kiso+=td_sub[i][1]
  bns+=1
  ans=max(ans,kiso+bns**2)
print(ans)




Fixed submission:
n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)

Buggy python submission (verdict: Runtime Error):
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=td[:k]
cat=list(set([tdi[0] for tdi in select]))
noselect=list(filter(lambda x: x[0] not in cat,td[k:]))
noselect.sort(key=lambda x:x[0])
noselect02=[]
noselect02.append(noselect[0])
for no in noselect[1:]:
    if no[0] != noselect[-1][0]:
        noselect.append(no)
        continue
    if no[1] > noselect[-1][1]:
        noselect[1]=no[1]

rs = sum([tdi[1] for tdi in select])+len(set([tdi[0] for tdi in select]))**2
for i in range(1,min(k,len(noselect)+1)):
    t = select[:-i]
    t[k-i:k-i] = noselect[:i]
    r = sum([tdi[1] for tdi in t])
    r += len(set([tdi[0] for tdi in t]))**2
    if rs < r:
        rs = r
print(rs)

Fixed submission:
n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)

Buggy python submission (verdict: Runtime Error):
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=td[:k]
cat=list(set([tdi[0] for tdi in select]))
noselect=[]
tdk=td[k:]
tdk.sort(key=lambda x:x[0])
noselect.append(tdk[0])
for no in tdk[1:]:
    if no[0] != noselect[-1][0]:
        noselect.append(no)
        continue
    if no[1] > noselect[-1][1]:
        noselect[1]=no[1]

rs = sum([tdi[1] for tdi in select])+len(set([tdi[0] for tdi in select]))**2
for i in range(1,min(k,len(noselect)+1)):
    t = select[:-i]
    t[k-i:k-i] = noselect[:i]
    r = sum([tdi[1] for tdi in t])
    r += len(set([tdi[0] for tdi in t]))**2
    if rs < r:
        rs = r
print(rs)

Fixed submission:
n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))


Fixed submission:
n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
noselect=deque(noselect)
while len(select) < k:
    select.append(noselect.popleft())
    i+=1
select.sort(key=lambda x:x[1])
select=deque(select)
cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))

Fixed submission:
n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)