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])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
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])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if len(L)==0:break
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x: x[1])
type=set([a[i][0] for i in range(k)])
dsum=sum([x[1] for x in a[:k]])
tnum=dict()
for i in [x[0] for x in a[:k]]:
    if i not in tnum.keys():
        tnum[i]=1
    else:tnum[i]+=1
ans=dsum+len(type)**2
sushi=a[-(n-k+1)::-1]
for i in a[k:]:
    if i[0] not in type:
        type.add(i[0])
        for x in sushi[:]:
            if tnum[x[0]]>1:
                tnum[x[0]]-=1
                dsum=dsum+i[1]-x[1]
                ans=max(ans,dsum+len(type)**2)
                break
            sushi.remove(x)
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])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if len(L)==0:break
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x: x[1])
type=set([a[i][0] for i in range(k)])
dsum=sum([x[1] for x in a[:k]])
tnum={i:[x[0] for x in a[:k]].count(i) for i in type}
ans=dsum+len(type)**2
sushi=a[-(n-k+1)::-1]
for i in a[k:]:
    if i[0] not in type:
        type.add(i[0])
        for x in sushi:
            if tnum[x[0]]>1:
                tnum[x[0]]-=1
                sushi.remove(x)
                dsum=dsum+i[1]-x[1]
                ans=max(ans,dsum+len(type)**2)
                break
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])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if len(L)==0:break
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
print(ans)