Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
l=len(kinds)
ans+=(l**2)

ans_=ans
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            ans_=max(ans,ans_)
            l+=1

print(ans_)


Fixed submission:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
ans+=(len(kinds)**2)

ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-len(kinds)**2+(len(kinds)+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            ans_.append(ans)

print(max(ans_))


Fixed submission:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])
#print(td)
ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
ans+=(len(kinds)**2)
#kindsの中はソートされている状況
#print(kinds)
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-len(kinds)**2+(len(kinds)+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            kinds[td[i][0]]=[td[i][1]]
            ans_.append(ans)
#print(kinds)
print(max(ans_))

Fixed submission:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])
#print(td)
ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
ans+=(len(kinds)**2)
#kindsの中はソートされている状況
#print(kinds)
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi=[1000000000,1000000000]:
            break
        else:
            ans=ans-len(kinds)**2+(len(kinds)+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            kinds[td[i][0]]=[td[i][1]]
            ans_.append(ans)
#print(kinds)
print(max(ans_))

Fixed submission:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])
#print(td)
ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
ans+=(len(kinds)**2)
#kindsの中はソートされている状況
#print(kinds)
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[-1,-1]:
            break
        else:
            ans=ans-len(kinds)**2+(len(kinds)+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            kinds[td[i][0]]=[td[i][1]]
            ans_.append(ans)
#print(kinds)
print(max(ans_))

Fixed submission:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)