Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
nums = []
for i in range(N):
    t, d = map(int, input().split())
    nums.append((d, t))
nums.sort(reverse=True)
se = set()
kind = 0
a1 = []
a2 = []
rest = []
for i, n in nums:
    if i < K:
        if not n[1] in se:
            se.add(n[1])
            kind += 1
            a1.append(n)
        else:
            a2.append(n)
    else:
        rest.append(n)
points = 0
for (d, t) in a1: points += d
for (d, t) in a2: points += d
ans = points + pow(kind, 2)
a2.sort()
for i, (d, t) in enumerate(rest):
    if t in se: continue
    if i >= len(a2): break
    points -= a2[i]
    points += d
    kind += 1
    ans = max(ans, points+pow(kind, 2))
print(ans)


Fixed submission:
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)


Fixed submission:
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in (maxs+other):
    ans += num
print(ans)


Fixed submission:
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in (maxs+other):
    ans += num
print(ans)


Fixed submission:
N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)