Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(x) for x in input().split()]

# sushi
s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)

# 各スシのMax
m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)

# スシ種類
# kinds = len(set([k for k in s.keys()]))
kinds = len(m)

ans = 0
for i in range(1, min(K, kinds) + 1):
    addM = m[:i]
    addAll2 = all2[:K - i]
    newAns = sum(addM) + sum(addAll2) + i ** 2
    ans = max(ans, newAns)

print(ans)



Fixed submission:
N, K = [int(x) for x in input().split()]

# sushi
s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)

# 各スシのMax
m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)

# スシ種類
# kinds = len(set([k for k in s.keys()]))
kinds = len(m)

import itertools

acM = list(itertools.accumulate(m))
acAll2 = list(itertools.accumulate(all2))

ans = 0
# for i in range(1, min(K, kinds) + 1):
for i in range(0, min(K, kinds)):
    # addM = m[:i]
    # addAll2 = all2[:K - i]
    # newAns = sum(addM) + sum(addAll2) + i ** 2
    t1 = acM[i]
    idx = K - i - 2
    t2 = acAll2[idx] if idx >= 0 and idx < len(acAll2)  else 0
    newAns = t1 + t2 + (i + 1) ** 2
    ans = max(ans, newAns)

print(ans)

pass

Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(x) for x in input().split()]

# sushi
s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)

# 各スシのMax
m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)

# スシ種類
# kinds = len(set([k for k in s.keys()]))
kinds = len(m)

ans = 0
for i in range(1, min(K, kinds) + 1):
    addM = m[:i]
    addAll2 = all2[:K - i]
    newAns = sum(addM) + sum(addAll2) + i ** 2
    ans = max(ans, newAns)

print(ans)



Fixed submission:
N, K = [int(x) for x in input().split()]

# sushi
s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)

# 各スシのMax
m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)

# スシ種類
# kinds = len(set([k for k in s.keys()]))
kinds = len(m)

import itertools

acM = list(itertools.accumulate(m))
acAll2 = list(itertools.accumulate(all2))

ans = 0
# for i in range(1, min(K, kinds) + 1):
for i in range(0, min(K, kinds)):
    # addM = m[:i]
    # addAll2 = all2[:K - i]
    # newAns = sum(addM) + sum(addAll2) + i ** 2
    t1 = acM[i]
    idx = K - i - 2
    t2 = acAll2[idx] if idx >= 0 and idx < len(acAll2)  else 0
    newAns = t1 + t2 + (i + 1) ** 2
    ans = max(ans, newAns)

print(ans)

pass