Buggy python submission (verdict: Time Limit Exceeded):
from  operator import itemgetter

# 満足ポイントを求める関数
def f(a, b):
    return len(a) ** 2 + sum(a) + sum(b)

n, k = map(int, input().split())

sushi = []
for i in range(n):
    sushi.append(list(map(int, input().split())))

sushi.sort(key=itemgetter(1), reverse=True)

s = []
s_change = []
types = []
# 集合Sの生成
for i in range(k):
    if sushi[i][0] not in types:
        s.append(sushi[i])
        types.append(sushi[i][0])
    else:
        s_change.append(sushi[i])

s_change.sort(key=itemgetter(1))
#print(s)
#print(s_change)

m = []
# 交換用の集合の生成
for i in range(k, n):
    if sushi[i][0] not in types:
        m.append(sushi[i])
        types.append(sushi[i][0])

#print(m)
#print([l[1] for l in s])
g = []
g.append(f([l[1] for l in s], [l[1] for l in s_change]))

# 集合gを求める
for i in range(min(len(s_change), len(m))):
    s.append(m[i])
    s_change.pop(0)
    g.append(f([l[1] for l in s], [l[1] for l in s_change]))

print(max(g))



Fixed submission:
# 入力
n, k = map(int, input().split())
A = [] # 寿司のネタの美味しさと種類を入れるリスト
for _ in range(n):
    A.append(list(map(int, input().split())))

# 美味しさ順にソートする
A.sort(key=lambda x: x[1], reverse=True)

# 美味しさで貪欲にとる
X = [] # 同じ種類で他に美味しさの大きい寿司が存在する
Y = [] # 取った寿司の中の各々の種類で美味しさが最も大きい
st = set() # 種類
for i in range(k):
    t, d = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)

# 美味しさポイントを求める
x = sum(X)
y = sum(Y)
v = len(Y) # 種類数
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    t, d = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from  operator import itemgetter
import numpy as np

n, k = map(int, input().split())

sushi = []
for i in range(n):
    sushi.append(list(map(int, input().split())))

#print(sushi)

sushi.sort(key=itemgetter(1), reverse=True)

#print(sushi)

sushi = np.array(sushi)

#print(sushi)

total = len(set(sushi[:,0]))

#print(total)

initial = len(set(sushi[:k, 0]))

#print(initial)

g = []

#print(initial, total)
for i in range(initial, min(total, k)+1):
    check = [0 for i in range(n)]
    value = i * i
    types = []
    s = 0
    for j in range(i):
        while True:
            if sushi[s, 0] not in types:
                types.append(sushi[s, 0])
                value += sushi[s, 1]
                check[s] = 1
                s += 1
                break
            s += 1

    s = 0

    for j in range(k-i):
        while True:
            if check[s] == 0:
                value += sushi[s, 1]
                s += 1
                break
            s += 1
    
    g.append(value)

#print(g)
print(max(g))
        

Fixed submission:
# 入力
n, k = map(int, input().split())
A = [] # 寿司のネタの美味しさと種類を入れるリスト
for _ in range(n):
    A.append(list(map(int, input().split())))

# 美味しさ順にソートする
A.sort(key=lambda x: x[1], reverse=True)

# 美味しさで貪欲にとる
X = [] # 同じ種類で他に美味しさの大きい寿司が存在する
Y = [] # 取った寿司の中の各々の種類で美味しさが最も大きい
st = set() # 種類
for i in range(k):
    t, d = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)

# 美味しさポイントを求める
x = sum(X)
y = sum(Y)
v = len(Y) # 種類数
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    t, d = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)

print(ans)