Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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

Buggy python submission (verdict: Time Limit Exceeded):
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))

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

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

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

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

    kind_cnt += 1
    idx -= 1

# print(kind_cnt)
print(max_pt)


Fixed submission:
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