Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append((t - 1, d))
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append((t - 1, d))
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N, K = map(int, input().split())

sushi_dict = defaultdict()

for i in range(N):
    t, d = map(int, input().split())
    if t in sushi_dict:
        sushi_dict[t].append(d)
    else:
        sushi_dict[t] = [d]
# print(sushi_dict)

max_array = []
for key, value in sushi_dict.items():
    value.sort()
    max_array.append((key, value[-1]))

max_array = sorted(max_array, key=lambda x: -x[1])

if K == 1:
    print(max_array[0][1] + 1)
    exit()

start_kind = min(K, len(max_array))
# print(max_array, start_kind)
ans = 0
for i in range(start_kind):
    ans += max_array[i][1]
ans += start_kind * start_kind
can_use_index = [max_array[i][0] for i in range(start_kind)]
can_use_num = []
for key, value in sushi_dict.items():
    if key not in can_use_index:
        continue
    for j in value[:-1]:
        can_use_num.append(j)

can_use_num = sorted(can_use_num,key=lambda x: -x)

use_num_count = K - start_kind
ans += sum(can_use_num[:use_num_count])
# print(can_use_num)
# print(use_num_count, start_kind)
for i in range(start_kind - 1):
    if use_num_count + i >= len(can_use_num):
        break
    ans_new = can_use_num[use_num_count + i] + (start_kind - 1 - i) * (
        start_kind - 1 - i)
    ans_old = max_array[start_kind - 1 - i][1] + (start_kind - i) * (
        start_kind - i)
    # print(ans_new, ans_old)
    if ans_new > ans_old:
        ans += (ans_new - ans_old)
    else:
        break
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N, K = map(int, input().split())

sushi_dict = defaultdict()

for i in range(N):
    t, d = map(int, input().split())
    if t in sushi_dict:
        sushi_dict[t].append(d)
    else:
        sushi_dict[t] = [d]
# print(sushi_dict)

max_array = []
for key, value in sushi_dict.items():
    value.sort()
    max_array.append((key, value[-1]))

max_array = sorted(max_array, key=lambda x: -x[1])

if K == 1:
    print(max_array[0][1] + 1)
    exit()

start_kind = min(K, len(max_array))
# print(max_array, start_kind)
ans = 0
for i in range(start_kind):
    ans += max_array[i][1]
ans += start_kind * start_kind
can_use_index = [max_array[i][0] for i in range(start_kind)]
can_use_num = []
for key, value in sushi_dict.items():
    if key not in can_use_index:
        continue
    for j in value[:-1]:
        can_use_num.append(j)

can_use_num = sorted(can_use_num,key=lambda x: -x)

use_num_count = K - start_kind
ans += sum(can_use_num[:use_num_count])
# print(can_use_num)
# print(use_num_count, start_kind)
for i in range(start_kind - 1):
    if use_num_count + i >= len(can_use_num):
        break
    ans_new = can_use_num[use_num_count + i] + (start_kind - 1 - i) * (
        start_kind - 1 - i)
    ans_old = max_array[start_kind - 1 - i][1] + (start_kind - i) * (
        start_kind - i)
    # print(ans_new, ans_old)
    if ans_new > ans_old:
        ans += (ans_new - ans_old)
    else:
        break
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)