Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq


def main():
    N, K = list(map(int, input().split(' ')))
    sushi_list = [list(map(int, input().split(' '))) for _ in range(N)]  # list of (neta, oishisa)
    sushi_list.sort(key=lambda x: x[1], reverse=True)  # sort by oishisa
    # check sushi with top K oishisa
    top_k_neta_num = len(set([s[0] for s in sushi_list[:K]]))
    top_k_oishisa = sum([s[1] for s in sushi_list[:K]])
    if top_k_neta_num == K:
        print(top_k_neta_num**2 + top_k_oishisa)
        return
    # check sushi of top_k_neta_num ~ K neta
    top_k_sushi = defaultdict(list)
    rest_sushi = defaultdict(list)
    for i, s in enumerate(sushi_list):
        if i < K:
            heapq.heappush(top_k_sushi[s[0]], s[1])
        else:
            heapq.heappush(rest_sushi[s[0]], - s[1])  # max-> min
    for neta in top_k_sushi.keys():
        if neta in rest_sushi:
            del rest_sushi[neta]
    max_point = top_k_neta_num**2 + top_k_oishisa
    point = max_point
    neta_num = top_k_neta_num
    for _ in range(K - top_k_neta_num):
        min_oishisa = 10**10
        min_oishisa_neta = 0
        for neta, oishisa in top_k_sushi.items():
            if len(oishisa) > 1 and oishisa[0] < min_oishisa:
                min_oishisa = oishisa[0]
                min_oishisa_neta = neta
        new_max_oishisa = 0
        new_max_oishisa_neta = 0
        for neta, oishisa in rest_sushi.items():
            if len(oishisa) > 0 and - oishisa[0] > new_max_oishisa:
                new_max_oishisa = - oishisa[0]
                new_max_oishisa_neta = neta
        # update top K sushi
        if min_oishisa_neta > 0 and new_max_oishisa_neta > 0:
            point += new_max_oishisa - min_oishisa + 2 * neta_num + 1
            neta_num += 1
            if point > max_point:
                max_point = point
            heapq.heappop(top_k_sushi[min_oishisa_neta])
            heapq.heappush(top_k_sushi[new_max_oishisa_neta], new_max_oishisa)
            del rest_sushi[new_max_oishisa_neta]
    print(max_point)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, K = list(map(int, input().split()))
    sushi_list = list()
    for _ in range(N):
        t, d = list(map(int, input().split()))
        t -= 1
        sushi_list.append((t, d))
    sushi_list.sort(key=lambda s: s[1], reverse=True)  # おいしさの降順でソート
    # おいしさTop Kのすしをとるのを初期解とする
    neta_flag_list = [0] * N
    topk_extra_sushi_list = list()  # Top Kのすしで、各ネタ最大のおいしさはないすし
    additional_sushi_list = list()  # Top Kのすしのネタ以外で、各ネタの最大のおいしさのすし
    point_topk = 0
    for k, sushi in enumerate(sushi_list):
        if k < K:
            if neta_flag_list[sushi[0]] == 1:
                topk_extra_sushi_list.append(sushi)
            point_topk += sushi[1]
        else:
            if neta_flag_list[sushi[0]] == 0:
                additional_sushi_list.append(sushi)
        neta_flag_list[sushi[0]] = 1
    n_neta = K - len(topk_extra_sushi_list)
    point_topk += n_neta ** 2
    # その他のネタをt種類追加する場合を考えて、初期解と比較していく
    d_extra, d_additional = 0, 0
    ans = point_topk
    n_additional_neta = min(K - n_neta, len(topk_extra_sushi_list), len(additional_sushi_list))
    for t in range(1, n_additional_neta + 1):
        n_cur_neta = n_neta + t
        d_extra += topk_extra_sushi_list[-t][1]
        d_additional += additional_sushi_list[t - 1][1]
        point = point_topk - d_extra + d_additional + (n_cur_neta**2 - n_neta**2)
        ans = max(ans, point)
    print(ans)


if __name__ == '__main__':
    main()