CodeEff/ECCO huggingface dataset:
# Original solution
import heapq

N, K = list(map(int, input().split()))
sushi = []
for i in range(N):
    t, d = list(map(int, input().split()))
    heapq.heappush(sushi, (-d, t))

total = 0
types = []
remain = []
for i in range(K):
    d, t = heapq.heappop(sushi)
    total -= d
    if t not in types:
        types.append(t)
    else:
        # 余りの寿司はremainにappend
        heapq.heappush(remain, -d)

types_len = len(types)
ans = total + types_len ** 2

while sushi and remain:
    d, t = heapq.heappop(sushi)
    if t not in types:
        types.append(t)
        remain_d = heapq.heappop(remain)
        total = total - d - remain_d
        types_len += 1
        ans = max(ans, total + types_len ** 2)

print(ans)


# Optimized solution
import heapq

N, K = list(map(int, input().split()))
sushi = []
for i in range(N):
    t, d = list(map(int, input().split()))
    heapq.heappush(sushi, (-d, t))

total = 0
types = set()
remain = []
for i in range(K):
    d, t = heapq.heappop(sushi)
    total -= d
    if t not in types:
        types.add(t)
    else:
        # 余りの寿司はremainにappend
        heapq.heappush(remain, -d)

types_len = len(types)
ans = total + types_len ** 2

while sushi and remain:
    d, t = heapq.heappop(sushi)
    if t not in types:
        types.add(t)
        remain_d = heapq.heappop(remain)
        total = total - d - remain_d
        types_len += 1
        ans = max(ans, total + types_len ** 2)

print(ans)
# Original solution
n,k=list(map(int, input().split()))
a=sorted([list(map(int, input().split())) for i in range(n)], key=lambda x:-x[1])
q=[]
ans=0
s=set()
for i in range(k):
    ans+=a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
ans+=len(s)**2
k1=k
ans1=ans
while k1<n and q:
    if a[k1][0] not in s:
        ans1=ans1+a[k1][1]-q.pop()-len(s)**2+(len(s)+1)**2
        ans=max(ans,ans1)
        s.add(a[k1][0])
    k1+=1
print(ans)


# Optimized solution
N, K = list(map(int, input().split()))
TD = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: -x[1])
q = []
ans = 0
s = set()
for i in range(K):
    ans += TD[i][1]
    if TD[i][0] in s:
        q.append(TD[i][1])
    s.add(TD[i][0])
ans += len(s) ** 2
k1 = K
ans1 = ans
while k1 < N and q:
    if TD[k1][0] not in s:
        ans1 = ans1 + TD[k1][1] - q.pop() - len(s) ** 2 + (len(s) + 1) ** 2
        ans = max(ans, ans1)
        s.add(TD[k1][0])
    k1 += 1
print(ans)
# Original solution
from collections import defaultdict as dd
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda x:-x[1])
used = set()
q1 = dd(list)
q2, q3 = [], []

score, kind = 0, 0

for t, d in l[:K]:
    score += d
    if t in used:
        heappush(q3, d)
    else:
        used.add(t)
        kind += 1

for t, d in l[K:]:
    if not t in used:
        heappush(q1[t], -d)
for t in list(q1.keys()):
    d = heappop(q1[t])
    heappush(q2, d)

ans = score + kind*kind
while q2 and q3:
    d1 = heappop(q2)
    d2 = heappop(q3)
    score -= d1+d2
    kind += 1
    ans = max(ans, score + kind*kind)

print(ans)

# Optimized solution
from collections import defaultdict as dd
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda x:-x[1])
used = set()
q1 = dd(list)
q2, q3 = [], []

score, kind = 0, 0

for t, d in l[:K]:
    score += d
    if t in used:
        heappush(q3, d)
    else:
        used.add(t)
        kind += 1

for t, d in l[K:]:
    if not t in used:
        heappush(q1[t], -d)
for t in list(q1.keys()):
    d = heappop(q1[t])
    heappush(q2, d)

ans = score + kind*kind
while q2 and q3:
    score -= heappop(q2)+heappop(q3)
    kind += 1
    ans = max(ans, score + kind*kind)

print(ans)
# Original solution
from collections import defaultdict
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
TD = []

for _ in range(N):
  TD.append(tuple(map(int, input().split())))

TD.sort(key = lambda x:x[1], reverse=True)
TD += [(TD[-1][0], 0)]

D = defaultdict(list)
T = [0]*N
H = []
ans = 0

for i in range(K):
  t, d = TD[i]
  T[t-1] += 1
  D[t].append(d)
  ans += d

cnt = sum(1 for c in T if c >= 1)
ans += cnt**2

for t in range(1, N+1):
  if T[t-1] >= 2:
    heappush(H, (D[t].pop(), t))
    T[t-1] -= 1

#print(ans, H, T, cnt)
for i in range(K, N):
  if H:
    t1, d1 = TD[i]
    d2, t2 = heappop(H)
    #print(t1, d1, t2, d2)
    if T[t1-1] == 0 and d1 - d2 + 2*cnt + 1 >= 0:
      ans += d1 - d2 + 2*cnt + 1
      cnt += 1
      T[t1-1] += 1
      if T[t2-1] >= 2:
        T[t2-1] -= 1
      if T[t2-1] >= 2:
        heappush(H, (D[t2].pop(), t2))
    else:
      heappush(H, (d2, t2))
    #print(ans, H, T, cnt)

#元のやつとの組み合わせ...？
ans2 = 0
T2 = [0]*N
D2 = []
cnt2 = 0
 
for t, d in TD:
  if cnt2 < K:
    if T2[t-1]:
      D2.append(d)
    else:
      T2[t-1] = 1
      ans2 += d
      cnt2 += 1

ans2 += sum(D2[:K-cnt2]) + sum(T2)**2

print((max(ans, ans2)))

# Optimized solution
from collections import defaultdict
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
TD = []

for _ in range(N):
  TD.append(tuple(map(int, input().split())))

TD.sort(key = lambda x:x[1], reverse=True)
TD += [(TD[-1][0], 0)]

D = defaultdict(list)
T = [0]*N
H = []
ans = [0]

for i in range(K):
  t, d = TD[i]
  T[t-1] += 1
  D[t].append(d)
  ans[0] += d

cnt = sum(1 for c in T if c >= 1)
ans[0] += cnt**2

for t, d in TD:
  if T[t-1] >= 2:
    heappush(H, (D[t].pop(), t))
    T[t-1] -= 1

#print(ans, H, T, cnt)
for i in range(K, N):
  if H:
    t1, d1 = TD[i]
    d2, t2 = heappop(H)
    #print(t1, d1, t2, d2)
    if T[t1-1] == 0:
      ans.append(ans[-1] + d1 - d2 + 2*cnt + 1)
      cnt += 1
      T[t1-1] += 1
    else:
      heappush(H, (d2, t2))
    #print(ans, H, T, cnt)

print((max(ans)))
#print(ans)
# Original solution

from collections import deque
n,k= list(map(int,input().split()))
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print((sum([tdi[1] for tdi in select])+(len(cat)**2)))


# Optimized solution
n,k= list(map(int,input().split()))
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
A=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        TOP.append(tdi[1])
        y+=1
    else:
        A.append(tdi[1])
    x+=tdi[1]
    
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k-1,len(A),len(SUB))):
    x -= A.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)
# Original solution
import queue
from collections import Counter
from operator import itemgetter

N, K = list(map(int, input().split()))
td = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(1), reverse=True)
group = queue.PriorityQueue()
count = Counter()
ans = 0

for t, d in td[:K]:
    group.put([d, t])
    count[t] += 1
    ans += d
ans += len(count) ** 2

s = queue.PriorityQueue()
s_count = Counter()
for t, d in td[K:]:
    if not count[t] and not s_count[t]:
        s.put([-d, t])
        s_count[t] += 1

n = ans
x = len(count)
while group.qsize():
    d, t = group.get()
    if count[t] != 1:
        count[t] -= 1
        n -= (d + x**2)

        d_, t_ = s.get()
        count[t_] += 1
        x += 1
        n += (-d_ + x**2)
        ans = max(ans, n)
print(ans)

# Optimized solution
import heapq

N, K = list(map(int, input().split()))
td = []
td_ = []
group = set()
total = 0

for i in range(N):
    t, d = list(map(int, input().split()))
    heapq.heappush(td, (-d, t))

for i in range(K):
    d, t = heapq.heappop(td)
    total -= d
    if t not in group:
        group.add(t)
    else:
        heapq.heappush(td_, -d)

ans = len(group)**2 + total

while td and td_:
    d, t = heapq.heappop(td)

    if t not in group:
        group.add(t)
        d_ = heapq.heappop(td_)
        total = total - d_ - d
        ans = max(ans, len(group)**2 + total)
print(ans)
# Original solution
n,k=list(map(int,input().split()))
a=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x: x[1])
type=set([a[i][0] for i in range(k)])
dsum=sum([x[1] for x in a[:k]])
tnum=dict()
for i in [x[0] for x in a[:k]]:
    if i not in list(tnum.keys()):
        tnum[i]=1
    else:tnum[i]+=1
ans=dsum+len(type)**2
sushi=a[-(n-k+1)::-1]
for i in a[k:]:
    if i[0] not in type:
        type.add(i[0])
        for x in sushi[:]:
            if tnum[x[0]]>1:
                tnum[x[0]]-=1
                dsum=dsum+i[1]-x[1]
                ans=max(ans,dsum+len(type)**2)
                break
            sushi.remove(x)
print(ans)




# Optimized solution
n, k = list(map(int, input().split()))
td = sorted([list(map(int, input().split())) for i in range(n)], reverse=True, key=lambda x: x[1])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if len(L)==0:break
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
print(ans)
# Original solution
N,K = list(map(int,input().split()))
s = [list(map(int,input().split())) for l in range(N)]
ans = []
s.sort(key = lambda x:x[1],reverse = True)
cnt = {}
A = 0
for i in range(K):
    if s[i][0] not in cnt:
        cnt[s[i][0]] = 1
    else:
        cnt[s[i][0]] += 1
    ans.append(s[i])
    A += s[i][1]
A += len(cnt)**2

ans.sort(key = lambda x:x[1])
for i in range(K,N):
    if s[i][0] not in cnt:
        for j in range(K):
            if cnt[ans[j][0]] >= 2:
                ans.pop(j)
                ans.insert(0,s[i])
                cnt[s[i][0]] = 1
                temp = 0
                for l in ans:
                    temp += l[1]
                A = max(A,temp+len(cnt)**2)
                    
                break
            
            
    else:
        continue

    if len(cnt) >= K:break
print(A)

# Optimized solution
N, K = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
 
# print(TD)
 
xs = sorted(TD, key=lambda x:-x[1])
 
#print(xs)
 
baset = 0
ts = set()
ds = []
 
for t, d in xs[:K]:
    baset += d
    if not t in ts:
        ts.add(t)
    else:
        ds.append(d)
result = baset + len(ts)**2
r = result

for t, d in xs[K:]:
    if not ds:
        break
    if t not in ts:
        r += 2*len(ts) + 1
        r += d - ds.pop()
        ts.add(t)
        result = max(r,result)

print(result)
# Original solution
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=A=0;l=[0]*-~n
for a,b in s[:k]:
 if l[a]:h.heappush(q,b)
 else:A+=z[v];v+=1
 l[a]=1;A+=b
T=A
for a,b in s[k:]:
 if l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1;A=max(A,T)
print(A)

# Optimized solution
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=T=A=0;l=[0]*-~n
for i,(a,b)in enumerate(s):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T)
print(A)
# Original solution
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=i=T=A=0;l=[0]*-~n
for a,b in s:
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

# Optimized solution
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];q=[];v=i=T=A=0;l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)
# Original solution
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = list(map(int, input().split()))
TD = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True, key=itemgetter(1))
L = [[] for _ in range(n+1)]
P = []
a = 0
cnt = 0
F = [-float("inf")]*(n+1)
B = 0
for t, d in TD[:k]:
  if B>>t & 1:
    heapq.heappush(P, d)
  else:
    B |= 1 << t
    a += 1
  cnt += d
F[a] = cnt
for i in range(a, n):
  if len(P) == 0:
    break
  while k < n and B>>TD[k][0] & 1:
    k += 1
  if k == n:
    break
  t, d = TD[k]
  B |= 1 << t
  F[i+1] = F[i] - heapq.heappop(P) + d
ans = 0
for i in range(a, n+1):
  ans = max(ans, F[i] + i*i)
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = list(map(int, input().split()))
TD = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True, key=itemgetter(1))
L = [[] for _ in range(n+1)]
P = []
a = 0
cnt = 0
F = [-float("inf")]*(n+1)
for t, d in TD[:k]:
  L[t].append(d)
  if len(L[t]) == 1:
    a += 1
  cnt += d
F[a] = cnt
for i in range(1, n+1):
  while len(L[i]) > 1:
    heapq.heappush(P, L[i].pop())
now = k
for i in range(a, n):
  if len(P) == 0:
    break
  while now < n and L[TD[now][0]]:
    now += 1
  if now == n:
    break
  t, d = TD[now]
  L[t].append(d)
  F[i+1] = F[i] - heapq.heappop(P) + d
ans = 0
for i in range(a, n+1):
  ans = max(ans, F[i] + i*i)
print(ans)
# Original solution
def p_d():
    from collections import defaultdict
    from heapq import heappush, heappop
    N, K = list(map(int, input().split()))
    li = []
    for _ in range(N):
        t, d = list(map(int, input().split()))
        li.append((t, d))
    li.sort(key=lambda x: x[1], reverse=True)
    sushi = defaultdict(list)
    ans = 0
    for i in range(K):
        heappush(sushi[li[i][0]], li[i][1])
        ans += li[i][1]
    ans += len(list(sushi.keys())) ** 2

    ans_list = [ans]
    while True:
        k, v = -1, 10 ** 9 + 1
        for key in list(sushi.keys()):
            if len(sushi[key]) > 1:
                tmp = heappop(sushi[key])
                if v > tmp:
                    if k != -1:
                        heappush(sushi[k], v)
                    k, v = key, tmp
                else:
                    heappush(sushi[key], tmp)
        if k == -1:
            break
        while K < N and li[K][0] in list(sushi.keys()):
            K += 1
        if K == N:
            break
        ans -= v
        ans -= len(list(sushi.keys())) ** 2
        heappush(sushi[li[K][0]], li[K][1])
        ans += li[K][1]
        ans += len(list(sushi.keys())) ** 2
        ans_list.append(ans)
    print((max(ans_list)))


if __name__ == '__main__':
    p_d()


# Optimized solution
def p_d():
    N, K = list(map(int, input().split()))
    inf = 10 ** 18
    sushi = [[-inf] for _ in range(N)]
    max_kind = -1
    for _ in range(N):
        t, d = list(map(int, input().split()))
        sushi[t - 1].append(d)
        if max_kind < t:
            max_kind = t
    for i in range(max_kind):
        sushi[i].sort(reverse=True)
    sushi.sort(key=lambda x: x[0], reverse=True)

    que = []
    res = 0
    for i in range(K):
        res += sushi[i][0]
        for j in sushi[i][1:]:
            que.append(j)
    que.sort()
    cur = res
    res += K ** 2
    for var in range(1, K)[::-1]:
        a = que.pop()
        b = sushi[var][0]
        cur += a - b
        res = max(res, cur + var ** 2)
    print(res)


if __name__ == '__main__':
    p_d()
# Original solution
from collections import Counter
N,K = list(map(int,input().split()))
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))
ans += len(selected)**2

tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)

# Optimized solution
N,K = list(map(int,input().split()))
TD = [tuple(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1])

import heapq
hq = []
heapq.heapify(hq)
selected = set()
ans = 0
for _ in range(K):
    t,d = TD.pop()
    if t in selected:
        heapq.heappush(hq, d)
    else:
        selected.add(t)
    ans += d
ans += len(selected)**2

tmp = ans
while TD:
    t,d = TD.pop()
    if t in selected: continue
    selected.add(t)
    if len(hq)==0: break
    tmp -= heapq.heappop(hq)
    tmp += d
    tmp += len(selected)*2 - 1
    ans = max(ans ,tmp)
print(ans)
# Original solution
from itertools import permutations

N, K = list(map(int, input().split()))
inputs = [[int(i) for i in input().split()] for _ in range(N)]

ans = 0
for items in permutations(inputs, K):
    tmp = 0
    sets = set()
    for i in range(K):
        tmp += items[i][1]
        sets.add(items[i][0])
    tmp += len(sets) * len(sets)
    ans = max(ans, tmp)

print(ans)


# Optimized solution
N, K = list(map(int, input().split()))

inputs = []
priority_queue = []
queue = []
sets = set()

for _ in range(N):
    key, value = list(map(int, input().split()))
    inputs.append((value, key))

inputs.sort(reverse=True) # valueで降順のソートをかけてる

for i in range(K):
    value, key = inputs[i]
    if key in sets:
        queue.append(value)
    else:
        priority_queue.append(value)
        sets.add(key)

sum_priority_queue = sum(priority_queue)
sum_queue = sum(queue)
kinds = len(sets)
ans = sum_priority_queue + sum_queue + kinds ** 2
for i in range(K, N):
    if not queue:
        break
    value, key = inputs[i]
    if key in sets:
        continue
    sets.add(key)
    sum_queue -= queue.pop()
    sum_priority_queue += value
    kinds += 1
    ans = max(ans, sum_priority_queue + sum_queue + kinds ** 2)

print(ans)
# Original solution
import itertools
N, K = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]

now = data[:K]


def count(x):
    p = len(set([a[0] for a in x]))
    point = p ** 2
    p = sum([a[1] for a in x])
    point += p
    return point

p_max = count(now)

for i in list(itertools.combinations(data,K)):
    if p_max < count(i):
        p_max = count(i)


print(p_max)


# Optimized solution
N, K = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]

data = sorted(data, key=lambda x: x[1], reverse=1)

now = data[:K]



def count(x):
    p = len(set([a[0] for a in x]))
    point = p ** 2
    p = sum([a[1] for a in x])
    point += p
    return point

p_max = count(now)


for i in data[K:]:
    if not i[0] in [a[0] for a in now]:
        for j in reversed(list(range(K))):
            if [a[0] for a in now].count(now[j][0]) != 1:
                now = now[:j]+now[j+1:]+[i]
                break
        if p_max < count(now):
            p_max = count(now)



print(p_max)
# Original solution
from collections import Counter
import heapq
n ,k = list(map(int, input().split()))

used = []
unused = []
for i in range(n):
    t, d = list(map(int, input().split()))
    unused.append((-d,t))
heapq.heapify(unused)
# 最初の集合
c = Counter()
ans = []
kiso = 0
for i in range(k):
    d, t = heapq.heappop(unused)
    kiso -= d
    c[t] += 1
    heapq.heappush(used,(-d, t))
bonus = len(c)
ans.append(kiso + bonus**2)

for i in range(k):
    # いらないものを抜く
    flag = False
    atode = []
    while used:
        d, t = heapq.heappop(used)
        if c[t] > 1:
            c[t] -= 1
            kiso -= d
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(used, i)
    # 全部の種類が1つしかない場合
    if not flag:break
    # 種類を増やす
    flag = False
    atode = []
    while unused:
        d, t = heapq.heappop(unused)
        if c[t]==0:
            bonus+=1
            kiso += -d
            c[t] += 1
            heapq.heappush(used, (-d, t))
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(unused, i)
    # 種類を増やせなかった場合
    if not flag:break
    ans.append(kiso + bonus**2)
print((max(ans)))

# Optimized solution
#参考 https://atcoder.jp/contests/abc116/submissions/4059000
n, k = list(map(int,input().split()))
# 価値の大きい順にソート, おいしさが前に来るようにした
sushi = sorted(list(map(int, input().split()))[::-1] for i in range(n))[::-1]
s = set()
# 二個以上あるものの集合があれば良い,かつ最小順
q = []
kiso = 0
for i in range(k):
    d, t = sushi[i]
    if t in s:
        q.append(d)
    else:
        s.add(t)
    kiso += d
ans = kiso + len(s)**2

# 減らせる ∧ 増やせる
i = k
while i < n and q:
    d, t = sushi[i]
    if t not in s:
        s.add(t)
        kiso += -q.pop()+d
        ans = max(ans, kiso+len(s)**2)
        continue
    i+=1
print(ans)
# Original solution
from heapq import heappush, heappop
N, K = list(map(int, input().split()))
TD = [list(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda x:x[1], reverse=True)
muptiple = set()
hp = []
for t, d in TD:
    flg = 0
    if t not in muptiple:
        muptiple.add(t)
        flg = 1
    heappush(hp, (d*-1, flg))

ret = []
point = 0
vari = 0
total = 0
for i in range(K):
    v = heappop(hp)
    t = v[0]*-1
    vari += v[1]
    point += t
    if not v[1]:
        heappush(ret, t)

total = vari ** 2 + point

while len(hp) > 0 and len(ret) > 0:
    v = heappop(hp)
    if v[1] == 0:
        continue
    pre_t = heappop(ret)
    t = v[0]*-1
    point -= pre_t - t
    vari += 1
    tmp = vari ** 2 + point
    total = max(total, tmp)

print(total)

# Optimized solution
from heapq import heappush, heappop
N, K = list(map(int, input().split()))
TD = [list(map(int, input().split())) for _ in range(N)]
TD.sort(key=lambda x:x[1], reverse=True)
muptiple = set()
for i in range(len(TD)):
    flg = 0
    if TD[i][0] not in muptiple:
        muptiple.add(TD[i][0])
        flg = 1
    TD[i][0] = flg
TD.reverse()
ret = []
point = 0
vari = 0
total = 0
for i in range(K):
    v = TD.pop()
    vari += v[0]
    point += v[1]
    if not v[0]:
        heappush(ret, v[1])

total = vari ** 2 + point

while len(TD) > 0 and len(ret) > 0:
    v = TD.pop()
    if v[0] == 0:
        continue
    pre_t = heappop(ret)
    point -= pre_t - v[1]
    vari += 1
    tmp = vari ** 2 + point
    total = max(total, tmp)

print(total)