There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i.
You are choosing K among these N pieces to eat.
Your "satisfaction" here will be calculated as follows:
 - The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
 - The base total deliciousness is the sum of the deliciousness of the pieces you eat.
 - The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.
You want to have as much satisfaction as possible.
Find this maximum satisfaction.

-----Constraints-----
 - 1 \leq K \leq N  \leq 10^5
 - 1 \leq t_i \leq N
 - 1 \leq d_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

-----Output-----
Print the maximum satisfaction that you can obtain.

-----Sample Input-----
5 3
1 9
1 7
2 6
2 5
3 1

-----Sample Output-----
26

If you eat Sushi 1,2 and 3:
 - The base total deliciousness is 9+7+6=22.
 - The variety bonus is 2*2=4.
Thus, your satisfaction will be 26, which is optimal.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
nums = []
for i in range(N):
    t, d = list(map(int, input().split()))
    nums.append((d, t))
nums.sort(reverse=True)
se = set()
a1 = []
a2 = []
rest = []
for i, n in enumerate(nums):
    if i < K:
        if not n[1] in se:
            se.add(n[1])
            a1.append(n)
        else:
            a2.append(n)
    else:
        rest.append(n)
points = 0
for (d, t) in a1: points += d
for (d, t) in a2: points += d
ans = points + pow(len(se), 2)
a2.sort()
idx2 = 0
for i, (d, t) in enumerate(rest):
    if t in se: continue
    if len(a2) <= idx2: break
    points -= a2[idx2][0]
    idx2 += 1
    points += d
    se.add(t)
    ans = max(ans, points+pow(len(se), 2))
print(ans)


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)

types = set()
can_remove = []
d_sm = 0

for t, d in td[:k]:
	d_sm += d
	if t in types:
		can_remove.append(d)
	else:
		types.add(t)

type_cnt = len(types)

ans = d_sm + type_cnt ** 2

left = td[k:][::-1]

while can_remove and left:
	t, d = left.pop()
	if t not in types:
		types.add(t)
		d_rmv = can_remove.pop()
		d_sm += d - d_rmv
		type_cnt += 1
		ans = max(ans, d_sm + type_cnt ** 2)

print(ans)


n,k = map(int,input().split())
sushi = [[int(i) for i in input().split()] for _ in range(n)]
sushi.sort(key=lambda x: x[1],reverse=True)
eaten = [False]*n
d1 = [0]
d2 = [0]
for i in range(n):
    t,d = sushi[i]
    t -= 1
    if eaten[t]: d1.append(d1[-1]+d)
    else:
        eaten[t] = True
        d2.append(d2[-1]+d)
# print(d1)
# print(d2)
ans = 0
for i in range(1,k+1):
    if k-i >= len(d1): continue
    if i >= len(d2): continue
    ans = max(ans, d1[k-i] + d2[i] + i*i)
print(ans)

from collections import defaultdict
from heapq import heappop, heappush

N, K = 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)

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

for i, td in enumerate(TD):
  t, d = td[0], td[1]
  if i == K:
    break
  T[t] += 1
  D[t].append(d)
  ans[0] += d
  if T[t] >= 2:
    heappush(H, (D[t].pop(), t))
    T[t] -= 1

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

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

print(max(ans))

n,k=map(int,input().split())
td=[list(map(int,input().split()))[::-1]for _ in range(n)]
td.sort(reverse=1)
s=set()
ss=set()
a=[]
b=[]
c=[]
for i in range(n):
  if i<k:
    d,t=td[i]
    if t in s:
      b.append(d)
    else:
      a.append(d)
      s.add(t)
      ss.add(t)
  else:
    d,t=td[i]
    if t not in ss:
      c.append(d)
      ss.add(t)
c=c[::-1]
ls=len(s)
su=sum(a)+sum(b)
ans=ls*ls+su
for i in range(min(len(b),len(c))):
  ls+=1
  su-=b.pop()
  su+=c.pop()
  ans=max(ans,ls*ls+su)
print(ans)

import heapq
from operator import itemgetter

n, k = list(map(int, input().split()))
sushi = [tuple(map(int, input().split())) for _ in range(n)]

sushi.sort(key=itemgetter(1), reverse=True)
que = []
kind = set()
res = 0
for t, d in sushi[:k]:
    if t in kind:
        heapq.heappush(que, d)
    else:
        kind.add(t)
    res += d
res += len(kind)**2

val = res
for t, d in sushi[k:]:
    if not que:
        break
    if t in kind:
        continue
    val += -heapq.heappop(que) + d + len(kind)*2 + 1
    kind.add(t)
    res = max(res, val)

print(res)


n,k = map(int,input().split())
td = [list(map(int,input().split())) for i in range(n)]
td.sort(key=lambda x:x[1],reverse=True)
a = 0
ans = []
kind = [-1]*n
c = 0
min_p = []
for i in range(n):
    eat = False
    if i<k:
        a += td[i][1]
        eat = True
    else:
        if min_p:
            if kind[td[i][0]-1]<0:
                a -= (min_p.pop()-td[i][1])
                a += (c+1)**2-c**2
                ans.append(a)
                eat = True
    if eat:
        if kind[td[i][0]-1]<0:
            kind[td[i][0]-1]=1
            c+=1
        else:min_p.append(td[i][1])
    if i==k-1:
        a += c**2
        ans.append(a)
print(max(ans))

import heapq
N,K=map(int,input().split())
TD=[list(map(int,input().split())) for _ in range(N)]
TD.sort(key=lambda x:x[1], reverse=True)

NETA=set()
duplication=[]
heapq.heapify(duplication)
ans=0
for t,d in TD[:K]:
    if t in NETA:
        heapq.heappush(duplication,d)
    else:
        NETA.add(t)
    ans+=d

s=[-float("inf")]*(K+1)
cnt=len(NETA)
s[cnt]=ans
for t,d in TD[K:]:
    if t in NETA:
        continue
    else:
        if duplication:
            x=heapq.heappop(duplication)
            ans+=d-x
            NETA.add(t)
            cnt+=1
            s[cnt]=ans

for i in range(K+1):
    s[i]+=i*i
print(max(s))

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]

sushi.sort(key=lambda x: x[1], reverse=True)

used = [0 for _ in range(N)]
dup = []
deli = 0

for i in range(K):
    t, d = sushi[i]
    if used[t - 1]:
        dup.append(d)
    used[t - 1] = 1
    deli += d

vari = sum(used)
sat = vari**2 + deli

dup.sort(reverse=True)

for i in range(N - K):
    if not dup:
        break
    t, d = sushi[K + i]
    if used[t - 1]:
        continue
    used[t - 1] = 1
    deli -= dup.pop()
    deli += d
    vari += 1
    sat = max(sat, vari**2 + deli)

print(sat)

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)


def __starting_point():
    main()
__starting_point()

from collections import defaultdict

n, k = list(map(int, input().split()))
top = [0] * n
sub = []

for i in range(n):
    t, d = list(map(int, input().split()))
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

print(ans)


import heapq
N, K = map(int,input().split())
L1 = []
L2 = []
S = set()
val = 0

for _ in range(N):
    t, d = map(int,input().split())
    L1.append((d, t))

L1.sort(reverse = True)

for i in range(K):
    val += L1[i][0]
    if L1[i][1] in S:
        heapq.heappush(L2, L1[i][0])
    else:
        S.add(L1[i][1])

ans = val + len(S) ** 2

for i in range(K, N):
    if len(L2) == 0:
        break
    if not L1[i][1] in S:
        S.add(L1[i][1])
        val -= heapq.heappop(L2)
        val += L1[i][0]
        ans = max(ans, val + len(S) ** 2)

print(ans)

N,K,*L=map(int,open(0).read().split());L=L[::-1]
I=set();X=0;U=[];D=[]
for d,t in sorted(zip(*[iter(L)]*2))[::-1]:
	if t in I:D+=d,
	elif X<K:I|={t};U+=d,;X+=1
D+=0,;i=K-X
while X and U[-1]+2*X-1<=D[i]:U.pop();X-=1;i+=1
print(sum(U+D[:i])+X**2)

N, K = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
M = len(set([t for t, d in TD]))
 
TD.sort(key=lambda x: x[1], reverse=True)
p, S, V = 0, [], set()
for t, d in TD[:K]:
    p += d
    if t in V:
        S.append(d)
    else:
        V.add(t)
p += len(V) ** 2
ans = p
for t, d in TD[K:]:
    if len(S) == 0:
        break
    if t not in V:
        p += 2 * len(V) + 1 - S.pop() + d
        V.add(t)
        ans = max(ans, p)
print(ans)

import heapq as hq

n,k=map(int,input().split())
A=[]
S0=[] #種類が増えない寿司
S1=[] #種類が増える寿司
for i in range(n):
    t,d=map(int,input().split())
    A.append([t,d])
A=list(reversed(sorted(A)))

now=0
for i in range(n):
    t=A[i][0]
    d=A[i][1]
    if now==t:
        S0.append(-d)
    else:
        S1.append(-d)
        now=t
hq.heapify(S0)
hq.heapify(S1)
C=[] #消し得る寿司のストック(S0から出したもの)

x=0 #おいしさの合計
y=0 #種類数
for i in range(k):
    if len(S0)==0:
        x+=-hq.heappop(S1)
        y+=1
        continue
    if len(S1)==0:
        s0=-hq.heappop(S0)
        x+=s0
        hq.heappush(C,s0)
        continue
    if S1[0]<=S0[0]:
        x+=-hq.heappop(S1)
        y+=1
    else:
        s0=-hq.heappop(S0)
        x+=s0
        hq.heappush(C,s0)
ans=x+y**2

for i in range(min(len(S1),len(C))):
    c=hq.heappop(C)
    s1=-hq.heappop(S1)
    x+=s1-c
    y+=1
    ans=max(x+y**2,ans)
print(ans)

import heapq
N,K = map(int,input().split())
td = [list(map(int,input().split())) for i in range(N)]
td.sort(key = lambda x:-x[1])
sumn = [[] for i in range(N)]
for i in range(N):
    heapq.heapify(sumn[i])
ans = 0
kind = {}
for t,d in td[:K]:
    if t not in kind:
        kind[t] = 1
    else:
        kind[t] += 1
    heapq.heappush(sumn[t-1],d)
kinds = len(kind)
ans = sum(sum(i) for i in sumn)
ans1 = ans +kinds**2
rem = td[K:]
nex = 0
candel = []
heapq.heapify(candel)
for k,v in kind.items():
    for i in range(v-1):
        heapq.heappush(candel,heapq.heappop(sumn[k-1]))
if candel:
    qd = heapq.heappop(candel)
    while K+nex < N:
        if td[K+nex][0] not in kind:
            kind[td[K+nex][0]] = 1
            kinds += 1
            ans = ans - qd + td[K+nex][1]
            ans1 = max(ans1,ans+kinds**2)
            nex += 1
            if candel:
                qd = heapq.heappop(candel)
            else:
                break
        else:
            nex += 1
print(ans1)

N,K = map(int,input().split())
TD = [[int(j) for j in input().split()] for i in range(N)]
TD = sorted(TD,key=lambda x:-x[1])
point = 0
stack = []
kind = set()

for t,d in TD[:K]:
  point+=d
  if t in kind:
    stack.append(d)
  else:
    kind.add(t)

point+=len(kind)**2
ans = point

for t,d in TD[K:]:
  if not stack:
    break
  if not t in kind:
    point+=d-stack.pop()+2*len(kind)+1
    kind.add(t)
    ans=max(ans,point)

print(ans)

n,k=map(int,input().split())
TD=[]
for i in range(n):
  t,d=map(int,input().split())
  TD.append([t,d])
TD.sort(key=lambda x:x[1],reverse=True)
V=set()
S=[]
ans=0
for t,d in TD[:k]:
  ans+=d
  if t in V:
    S.append(d)
  else:
    V.add(t)
ans+=len(V)**2
x=ans
for t,d in TD[k:]:
  if S==[]:
    break
  if not t in V:
    x=x-S.pop()+d-len(V)**2+(len(V)+1)**2
    V.add(t)
    ans=max(x,ans)
print(ans)

#!/usr/bin/env python3

from collections import defaultdict

def main():
    n, k = list(map(int, input().split()))
    td = []
    for i in range(n):
        ti, di = list(map(int, input().split()))
        td.append((ti, di))
    td = list(reversed(sorted(td)))
    tdd = defaultdict(list)
    for t, d in td:
        tdd[t].append(d)

    a = []; b = []
    for _, v in list(tdd.items()):
        a.append(v[0])
        b += v[1:]

    a = list(reversed(sorted(a)))
    b = list(reversed(sorted(b)))
    for i in range(1, len(a)):
        a[i] += a[i - 1]
    for i in range(len(a)):
        a[i] += (i + 1) ** 2
    for i in range(1, len(b)):
        b[i] += b[i - 1]

    a = [0] + a
    b = [0] + b

    res = 0
    for i in range(1, k + 1):
        if i >= len(a) or (k - i) >= len(b):
            continue
        ts = a[i] + b[k - i]
        res = max(res, ts)

    print(res)

def __starting_point():
    main()

__starting_point()

n,k=map(int,input().split())
X=[]
for i in range(n):
    t,d=map(int,input().split())
    X.append([t,d])
    
X.sort(key=lambda x:x[1],reverse=True)

V=set()
point=0
S=[]

for t,d in X[:k]:
    point+=d
    if t in V:
        S.append(d)
    else:
        V.add(t)
point+=len(V)**2

ans=point

for t,d in X[k:]:
    if not S:
        break
    if not t in V:
        point+=d-S.pop()+1+len(V)*2
        V.add(t)
        ans=max(ans,point)

print(ans)

import sys
read = sys.stdin.readline
n, k = list(map(int, read().split()))
# 種類数を増やすときは、各種類で最もでかいのを食べる
# 種類数最大降順配列、他降順配列みたいなの用いしtえ
# 食べる出井数を全探索する
# 累積和
sushi = [[] for _ in range(n)]

for i in range(n):
    t, d = list(map(int, read().split()))
    t -= 1
    sushi[t].append(d)

max_sushi = []
other_sushi = []
for i in range(n):
    if len(sushi[i]) == 0:
        continue
    sushi[i].sort()
    max_sushi.append(sushi[i][-1])
    for j in range(len(sushi[i]) - 1):
        other_sushi.append(sushi[i][j])
max_sushi.sort(reverse=True)
other_sushi.sort(reverse=True)

for i in range(len(max_sushi) - 1):
    max_sushi[i + 1] += max_sushi[i]
for i in range(len(other_sushi) - 1):
    other_sushi[i + 1] += other_sushi[i]

a = len(max_sushi)
b = len(other_sushi)
ans = 0
for x in range(1, k + 1):
    if x > a or k - x > b:
        continue
    other = 0 if k - x - 1 < 0 else other_sushi[k - x - 1]
    ans = max(ans, x * x + max_sushi[x - 1] + other)
print(ans)


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    td = [list(map(int, input().split())) for _ in range(n)]
    td.sort(reverse=True, key=lambda a: a[1])
    delicious = 0
    syurui = set()
    suteru = []
    for i in range(k):
        t, d = td[i]
        delicious += d
        if  t in syurui:
            suteru.append(d)
        else:
            syurui.add(t)
    heapify(suteru)
    neta = len(syurui)
    res = delicious + neta**2
    for i in range(k, n):
        t, d = td[i]
        if t in syurui:
            continue
        if len(suteru)==0:
            print(res)
            return
        syurui.add(t)
        delicious += d - heappop(suteru)
        neta += 1
        res = max(res, delicious+neta**2)
    print(res)

def __starting_point():
    main()
__starting_point()

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)

types = set()
can_remove = []
d_sm = 0

for t, d in td[:k]:
	d_sm += d
	if t in types:
		can_remove.append(d)
	else:
		types.add(t)

type_cnt = len(types)

ans = d_sm + type_cnt ** 2

left = []
for t, d in td[k:]:
	d = -d
	heappush(left, [d, t])

while can_remove and left:
	d, t = heappop(left)
	d = -d
	if t not in types:
		types.add(t)
		d_rmv = can_remove.pop()
		d_sm += d - d_rmv
		type_cnt += 1
		ans = max(ans, d_sm + type_cnt ** 2)

print(ans)


# various sushi
import heapq
N, K = map(int, input().split())
que = []
for i in range(N):
    t, d = map(int, input().split())
    que.append((t, d))

que.sort(key=lambda x: -x[1])
NOW = que[:K]

N_set = set()

sums = 0

cnt = [0 for i in range(N+1)]  # ねたxに何個いるか
ng,ok,sub = [], [], []
heapq.heapify(ng)
heapq.heapify(ok)
heapq.heapify(sub)

for index, value in NOW:
    sums += value
    cnt[index] += 1
    heapq.heappush(ng, (value, index))
    N_set.add(index)
while ng:
    value, index = heapq.heappop(ng)
    if cnt[index] > 1:
        heapq.heappush(ok, (value, index))
        cnt[index] -= 1
    elif cnt[index] == 1:
        heapq.heappush(sub, (value, index))

ng = sub

# ng とっちゃダメなやつ
# ok とってもいいやつ

S = len(N_set)
ans = S**2+sums


# これより更新することはあるか？

for i in range(K, N):
    taste, value = que[i]
    if taste in N_set:
        pass
    else:
        #taste not in N_set
        if ok:
            min_value, m_taste = heapq.heappop(ok)
            sums -= min_value
            sums += value
            S += 1
            cnt[taste] += 1
            N_set.add(taste)
            cnt[m_taste] -= 1
            heapq.heappush(ng, (value, taste))
            ans = max(ans, S**2+sums)

print(ans)

N,K=map(int,input().split())
t=[list(map(int,input().split())) for _ in range(N)]
t.sort(key=lambda x:-x[1])
ans=0
dp=set()
p=[]
for i in range(K):
  ans+=t[i][1]
  if t[i][0] in dp:
    p.append(t[i][1])
  dp.add(t[i][0])
ans+=len(dp)**2
wer=ans
while K<N and p:
  if t[K][0] not in dp:
    wer=wer+t[K][1]-p.pop()-len(dp)**2+(len(dp)+1)**2
    ans=max(ans,wer)
    dp.add(t[K][0])
  K+=1
print(ans)

n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab_s = sorted(ab, key=lambda x: x[1])
ab_r = list(reversed(ab_s))

t = [x[0] for x in ab_r]
d = [x[1] for x in ab_r]        

t_set = len(set(t[:k]))
d_sum = sum(d[:k])

res = [t_set**2 + d_sum]

from collections import Counter
t_cou = Counter(t[:k])

dp =[0]*(n+1)
j_old = k-1

for i in t_cou:
    dp[i] = t_cou[i]

for i in range(k,n):
    t_new = ab_r[i][0]
    if dp[t_new] ==0:
        for j in range(j_old,-1,-1):
            t_old = ab_r[j][0]
            if dp[t_old] <=1:
                pass
            else:
                dp[t_new] =1
                dp[t_old] -=1
                t_set +=1
                d_sum = d_sum - ab_r[j][1] + ab_r[i][1]
                res.append(t_set**2 + d_sum)
                j_old = j-1
                break
            j_old = 0

print(max(res))

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    ss = sorted(zip(d, t), reverse=True)
    gs = []
    mst = set()
    for di, ti in ss[:K]:
        if ti in mst:
            gs.append((di, ti))
        else:
            mst.add(ti)
    dm = {}
    for di, ti in ss[K:]:
        if ti in dm or ti in mst:
            continue
        dm[ti] = di
    hs = sorted(((di, ti) for ti, di in list(dm.items())), reverse=True)
    cd = sum(di for di, ti in ss[:K])
    ct = len(mst)
    m = cd + ct * ct
    for (gdi, gti), (hdi, hti) in zip(reversed(gs), hs):
        cd += hdi - gdi
        ct += 1
        m = max(m, cd + ct * ct)
    print(m)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]"
    d = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)


def __starting_point():
    main()

__starting_point()

N,K,*L=list(map(int,open(0).read().split()))
S=sorted([(d,t)for t,d in zip(*[iter(L)]*2)],reverse=True)
In=set()
X=0
uni=[]
dub=[]
for d,t in S:
	if t not in In:
		In.add(t)
		uni.append(d)
		X+=1
		if X==K:
			break
	else:
		dub.append(d)
det=sum(dub[:K-X])
dub=dub[K-X:]
for d in dub:
	if uni[-1]+2*X-1<=d:
		uni.pop()
		X-=1
		det+=d
	else:
		break
print((sum(uni)+det+X**2))



from collections import defaultdict
N,K=map(int,input().split())

dtlist=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  dtlist.append((d,t))
  tset_all.add(t)
dtlist.sort()
#print(heapq)

dtlist_Krev=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  d,t=dtlist.pop()
  dtlist_Krev.append((d,t))
  dsum+=d
  tdic[t]+=1
dtlist_Krev.sort(reverse=True)

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,min(K,len(tset_all))+1):
  loop_flg=True
  while(loop_flg):    
    d,t=dtlist_Krev.pop()
    if tdic[t]>1:
      tdic[t]-=1
      dsum-=d
      
      while(True):        
        d2,t2=dtlist.pop()
        if tdic[t2]==0:
          tdic[t2]=1
          dsum+=d2
          loop_flg=False
          break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)

# D - Various Sushi
import sys
from collections import defaultdict
import heapq

readline = sys.stdin.readline

dd = defaultdict(list)
N, K = list(map(int, readline().split()))
for i in range(N):
    t, d = list(map(int, readline().split()))
    heapq.heappush(dd[t], d*-1)

dd = list(dd.values())
dd.sort()

ans = 0
fix = 0
var = []
len_var = 0
sum_var = 0
tmp_max = 0

for i in range(min(K, len(dd))):
    fix += heapq.heappop(dd[i]) * -1
    for _ in range(len(dd[i])):
        tmp = heapq.heappop(dd[i]) * -1
        heapq.heappush(var, tmp)
        len_var += 1
        sum_var += tmp
    while len_var > K-(i+1) and len_var > 0:
        del_var = heapq.heappop(var)
        len_var -= 1
        sum_var -= del_var
    if len_var == K-(i+1):
        ans = max(ans , fix+sum_var + (i+1)**2)

print(ans)


import heapq
n,k = list(map(int,input().split()))
L = []
for i in range(n):
    t,d = list(map(int,input().split()))
    L.append([d,t])
L.sort()
ans = []
cur = [0]*n
heap = []
var = 0
for i in range(k):
    if cur[L[n-i-1][1]-1] == 0:
        ans.append(L[n-i-1][0])
        cur[L[n-i-1][1]-1] = 1
        var += 1
    else:
        heapq.heappush(heap, L[n-i-1])
temp = 0
for i in range(len(ans)):
    temp += ans[i]
for i in range(len(heap)):
    temp += heap[i][0]
temp += var**2
now = temp
for i in range(n-k):
    if len(heap) != 0:
        a = heapq.heappop(heap)
        if cur[L[n-k-i-1][1]-1] == 0:
            ans.append(L[n-k-i-1][0])
            cur[L[n-k-i-1][1]-1] = 1
            now -= var**2
            now -= a[0]
            var += 1
            now += var**2
            now += L[n-k-i-1][0]
            temp = max(temp, now)
        else:
            heapq.heappush(heap, a)
print(temp)


from collections import defaultdict
from heapq import heappop, heappush

N, K = 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))

from heapq import heappop,heappush
n,k=map(int,input().split())
s=[]
h=set()#種類
l=[0]*n #個数について
for _ in range(n):
    t,d=map(int,input().split())
    s.append((d,t-1))
s=sorted(s,reverse=True)
a=[]#heapq
num=0#美味しさのわ
for i in range(k):
    d,t=s[i]
    l[t]+=1
    h.add(t)
    num+=d
    if l[t]>1:
        heappush(a,(d,t))#２種類以上ならheapqにたす
ans=len(h)**2+num
for j in range(k,n):
    d,t=s[j]#次に小さいのを引いてくる
    l[t]+=1
    if  l[t]>=2:
        continue #2以上ならむし
    if len(a)==0:
        break
    d1,t1=heappop(a) #いらないのを引く
    h.add(t)
    num=num-d1+d
    ans=max(ans,len(h)**2+num)
print(ans)

def resolve():
    N, K = list(map(int, input().split()))
    TD = sorted([list(map(int, input().split())) for _ in range(N)], reverse=True, key=lambda x: x[1])
    eat_types = set()
    eat_dups = []
    total = 0
    for i in range(K):
        typ, point = TD[i]
        total += point
        if typ in eat_types:
            eat_dups.append(TD[i])
        else:
            eat_types.add(typ)
    ans = total + len(eat_types)**2

    didx = len(eat_dups)-1
    for i in range(K, N):
        typ, point = TD[i]
        if typ in eat_types:
            continue
        if didx < 0:
            break
        total -= eat_dups[didx][1]
        total += point
        didx -= 1
        eat_types.add(typ)
        ans = max(ans, total+len(eat_types)**2)
    print(ans)
    
    
    
    

if '__main__' == __name__:
    resolve()

#!/usr/bin/env python3

from collections import deque
n, k = list(map(int, input().split()))

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

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

set_ = set()
val = 0
duplicated = deque([])

for t_tmp, d_tmp in td[:k]:
    val += d_tmp
    if t_tmp in set_:
        duplicated.append(d_tmp)
    else:
        set_.add(t_tmp)

now = val + len(set_)**2


nx = deque(td[k:])
ans = now
c = len(set_)
while len(set_) < k and nx:
    i, j = nx.popleft()
    if i in set_:
        continue
    d = duplicated.pop()
    diff = j-d + 2 * c + 1
    set_.add(i)
    ans = max(ans, now + diff)
    now += diff
    c += 1
print(ans)


n,k= 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)

n, k = map(int, input().split())
tds = []
for i in range(n):
    t, d = map(int, input().split())
    tds.append((d,t))
tds.sort(reverse=True)
cnt = k
hand = []
hand_throw = []
hs = {}
subs = []
rs = {}
v_t = {}
res = 0
for i in range(n):
    if cnt > 0:
        if tds[i][1] in hs:
            hs[tds[i][1]] += 1
            hand_throw.append(tds[i][0])
        else:
            hs[tds[i][1]] = 1
            hand.append(tds[i][0])
        cnt -= 1
        res += tds[i][0]
    else:
        if not tds[i][1] in rs and not tds[i][1] in hs:
            rs[tds[i][1]] = 1
            subs.append(tds[i][0])
    if not tds[i][1] in v_t:
        v_t[tds[i][1]] = 1
subs.sort()
v_hs = len(hs)
v_t = len(v_t)
res += pow(v_hs,2)
final_res = res
while v_hs+1 <= k and v_hs+1 <= v_t:
    res += subs.pop() - hand_throw.pop() - pow(v_hs,2) + pow(v_hs+1,2)
    final_res = max(final_res,res)
    v_hs += 1
print(final_res)

import heapq
n,k=map(int,input().split())
td=[[0]*2 for _ in range(n)]
for i in range(n):
    t,d=map(int,input().split())
    td[i][0],td[i][1]=d,t
td.sort(reverse=True)
di=set()
sa=[]
heapq.heapify(sa)
ans=0
for d,t in td[:k]:
    if t in di:
        heapq.heappush(sa, d)
    else:
        di.add(t)
    ans+=d

s=[-10**18]*(k+1)
cnt=len(di)
s[cnt]=ans
for d,t in td[k:]:
    if t in di:
        continue
    else:
        if sa:
            x=heapq.heappop(sa)
            ans+=d-x
            di.add(t)
            cnt+=1
            s[cnt]=ans

for i in range(k+1):
    s[i]+=i*i

print(max(s))

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

S.sort(key=lambda x: -x[1])
st = set()
first_acc, other_acc = [0], [0]
for t, d in S:
    if t in st:
        other_acc.append(other_acc[-1] + d)
    else:
        st.add(t)
        first_acc.append(first_acc[-1] + d)

ans = 0
for i in range(K + 1):
    if len(first_acc) <= i or len(other_acc) <= K - i:
        continue
    ans = max(ans, first_acc[i] + other_acc[K - i] + i * i)
print(ans)


from operator import itemgetter
n,k=map(int,input().split())
td=[list(map(int,input().split())) for _ in range(n)]
td.sort(key=itemgetter(1),reverse=True)
ans=0
kind=0
flg=[False]*n
sing,comp=[],[]
for i in range(n):
    t,d=td[i]
    t-=1
    if i<k:
        ans+=d
        if flg[t]:
            comp.append(d)
        else:
            flg[t]=True
            kind+=1
    else:
        if not flg[t]:
            sing.append(d)
            flg[t]=True
comp=comp[::-1]
cnt=ans
ans+=kind**2
#print(comp)
#print(sing)
if len(comp)>len(sing):
    for i in range(len(sing)):
        dc,ds=comp[i],sing[i]
        cnt+=ds-dc
        kind+=1
        ans=max(ans,cnt+kind**2)
else:
    for i in range(len(comp)):
        dc,ds=comp[i],sing[i]
        cnt+=ds-dc
        kind+=1
        ans=max(ans,cnt+kind**2)
print(ans)

from collections import Counter
from heapq import heappush, heappop

n, k = list(map(int, input().split()))
s = []
for _ in range(n):
    t, d = list(map(int, input().split()))
    s.append((d, t))
s.sort()
bp = 0
x = 0
c = Counter()
cand = []
for _ in range(k):
    d, t = s.pop()
    bp += d
    if c[t] == 0:
        x += 1
    c[t] += 1
    heappush(cand, (d, t))
ans = bp + x * x
while s:
    d, t = s.pop()
    if c[t] == 0:
        while cand:
            dd, td = heappop(cand)
            if c[td] == 1:
                continue
            else:
                c[td] -= 1
                bp -= dd
                break
        else:
            break
        bp += d
        x += 1
        c[t] = 1
        ans = max(ans, bp + x * x)
print(ans)


import collections
N,K = list(map(int,input().split()))
dic = {}
A = []
for _ in range(N):
    t,d = list(map(int,input().split()))
    A.append([t,d])
A.sort(key = lambda x:x[1], reverse = True)
val = 0
set_ = set()
duplicated = collections.deque([])
for t,d in A[:K]:
    val += d
    if t in set_:
        duplicated.append(d)
    else:
        set_.add(t)
now = val + len(set_)**2

nx = collections.deque(A[K:])
ans = now
c = len(set_)
while len(set_) < K and nx:
    i,j = nx.popleft()
    if i in set_:
        continue
    d = duplicated.pop()
    diff = j-d + 2*c+1
    set_.add(i)
    now += diff
    ans =max(ans,now)
    c += 1
print(ans)


N,K = 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)

# 解説と下記を参考に作成
# https://atcoder.jp/contests/abc116/submissions/16781289
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, td):
    max_t = [0] * (N + 1)
    for i in range(N):
        if max_t[td[i][0]] < td[i][1]:
            max_t[td[i][0]], td[i][1] = td[i][1], max_t[td[i][0]]
    d = [tdi[1] for tdi in td]
    max_t.sort(reverse=True)
    d.sort(reverse=True)
    c_sum_max_t = [0]
    for i in range(N + 1):
        c_sum_max_t.append(c_sum_max_t[-1] + max_t[i])
    c_sum_d = [0]
    for i in range(N):
        c_sum_d.append(c_sum_d[-1] + d[i])
    ans = 0
    kind = len([i for i in max_t if i > 0])
    for i in range(1, min(kind + 1, K + 1)):
        # print(c_sum_max_t[i], c_sum_d[K - i], i ** 2, c_sum_max_t[i] + c_sum_d[K - i] + i ** 2)
        ans = max(c_sum_max_t[i] + c_sum_d[K - i] + i ** 2, ans)
    print(ans)
    # return ans


def __starting_point():
    N, K = list(map(int, input().split()))
    td = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, K, td)

    # # test
    # from random import randint
    # from func import random_str
    # import tmp
    # import copy
    #
    # while True:
    #     N, K = 10, randint(1, 10)
    #     td = [[randint(1, N), randint(2, 10 ** 2)] for _ in range(N)]
    #     my = solve(N, K, copy.deepcopy(td))
    #     ot = tmp.resolve(N, K, td)
    #     if my != ot:
    #         print(N, K)
    #         for tdi in td:
    #             print(tdi[0], tdi[1])
    #         print()
    #         print(my, ot)
    #         break

__starting_point()

import heapq
n,k = list(map(int,input().split()))
L = []
for i in range(n):
    t,d = list(map(int,input().split()))
    L.append([d,t])
L.sort()
ans = []
cur = [0]*n
heap = []
var = 0
for i in range(k):
    if cur[L[n-i-1][1]-1] == 0:
        ans.append(L[n-i-1][0])
        cur[L[n-i-1][1]-1] = 1
        var += 1
    else:
        heapq.heappush(heap, L[n-i-1])
temp = 0
for i in range(len(ans)):
    temp += ans[i]
for i in range(len(heap)):
    temp += heap[i][0]
temp += var**2
now = temp
for i in range(n-k):
    if len(heap) != 0:
        a = heapq.heappop(heap)
        if cur[L[n-k-i-1][1]-1] == 0:
            cur[L[n-k-i-1][1]-1] = 1
            now -= var**2
            now -= a[0]
            var += 1
            now += var**2
            now += L[n-k-i-1][0]
            temp = max(temp, now)
        else:
            heapq.heappush(heap, a)
print(temp)


import sys
from operator import itemgetter
from heapq import *
input = sys.stdin.readline



def main():
    n, k = list(map(int, input().split()))
    sushi = [list(map(int, input().split())) for _ in range(n)]
    
    sushi.sort(key=itemgetter(1), reverse=True)
    
    key = []
    already = [False]*(n+1)
    variety = k
    taste = 0
    for i in range(k):
        v, t = sushi[i]
        taste += t
        if already[v]:
            variety -= 1
            heappush(key, t)
            continue
        already[v]= True
    
    ans = [variety**2+taste]
    for i in range(k, n):
        if variety == k:
            break
        v, t = sushi[i]
        if already[v]:
            continue
        already[v] = True
        taste += t-key[0]
        heappop(key)
        variety += 1
        ans.append(variety**2+taste)
        
    print((max(ans)))
    
    
        
   
    
def __starting_point():
    main()

__starting_point()

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)
td_core=[]
td_sel=[]
td_sub=[]
cat=[0]*(n+1)
for i in range(n):
  if i < k and cat[td[i][0]]==0:
    td_core.append(td[i])
    cat[td[i][0]]=1
  elif i < k:
    td_sel.append(td[i])
  elif cat[td[i][0]]==0:
    td_sub.append(td[i])
    cat[td[i][0]]=1
# i >= k and cat[td[i][0]]==1 となるものはすでにtd_core,td_sel,td_sub内ものと種類も被っている上に美味しさも低い
# 後の工程は種類を増やす処理なので、同じ種類のネタはそのネタの中で美味しさが最大のもの一つで十分。なので捨てる

# dの大きい順に貪欲にネタを取得したときの満足ポイント
kiso=sum([x[1] for x in td_core])+sum([x[1] for x in td_sel])
bns=len(td_core)
ans=kiso+bns**2
# この状態からネタの種類を増やしていき最大が出てくるか検証
# td_sel内のネタは同一ネタが複数あり、そのネタ内で最大じゃないものが美味しさの大きい順に入っている。
# td_subにはtd_core,td_selにないネタの最大美味しさの寿司が入っている。
td_sel.sort(key=lambda x:x[1])
for i in range(min(len(td_sel),len(td_sub))):
  kiso-=td_sel[i][1]
  kiso+=td_sub[i][1]
  bns+=1
  ans=max(ans,kiso+bns**2)
print(ans)


def main():
    from collections import deque
    n, k, *td = list(map(int, open(0).read().split()))
    s = list(zip(*[iter(td)] * 2))
    t = sorted(s, key=lambda x: x[1], reverse=True)

    variety = set()
    base = 0
    duplicated = deque([])

    for x, y in t[:k]:
        base += y
        if x in variety:
            duplicated.append(y)
        else:
            variety.add(x)

    now = base + len(variety) ** 2

    nx = deque(t[k:])
    c = len(variety)
    tmp = now
    while c < k and nx:
        i, j = nx.popleft()
        if i in variety:
            continue

        d = duplicated.pop()
        dif = j - d + 2 * c + 1
        variety.add(i)
        tmp = max(tmp, now + dif)
        now += dif
        c += 1

    print(tmp)


def __starting_point():
    main()

__starting_point()

from collections import defaultdict
import heapq
N,K=map(int,input().split())

hq=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  heapq.heappush(hq,(-d,t))
  tset_all.add(t)
#print(heapq)

hq_K=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  md,t=heapq.heappop(hq)
  heapq.heappush(hq_K,((-md,t)))
  dsum-=md
  tdic[t]+=1  

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,min(K,len(tset_all))+1):
  loop_flg=True
  while(loop_flg):
    d,t=heapq.heappop(hq_K)
    if tdic[t]>1:
      tdic[t]-=1
      dsum-=d
      
      while(True):
        md2,t2=heapq.heappop(hq)
        if tdic[t2]==0:
          tdic[t2]=1
          dsum-=md2
          loop_flg=False
          break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)

from heapq import heapify, heappush, heappop

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]
S.sort(key=lambda x: (-x[1]))
types = set()
RS = []
AS = []
d_sum = 0
for i in range(K):
  _type, value = S[i][0], S[i][1]
  if _type in types:
    heappush(RS, (value, _type))
  else:
    types.add(_type)
  d_sum += value
t_sum = len(types)
d_sum += pow(t_sum, 2)
for i in range(K, N):
  _type, value = S[i][0], S[i][1]
  if not _type in types:
    heappush(AS, (-value, _type))
    types.add(_type)
ans = d_sum
while len(AS) > 0 and len(RS) > 0:
  av, at = heappop(AS)
  rv, rt = heappop(RS)
  t_sum += 1
  d_sum += -av-rv+pow(t_sum, 2)-pow(t_sum-1, 2)
  ans = max(ans, d_sum)
print(ans)

N,K,*L = map(int, open(0).read().split())
ls = []
for i,(t,d) in enumerate(zip(*[iter(L)]*2)):
  ls.append((d,t))
ls.sort()
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
  d,t = ls.pop()
  ans += d
  if t not in S:
    num += 1
    S.add(t)
  else:
    pre.append(d)
pre.sort(reverse=True)
ans += num*num
if pre==[]:
  print(ans)
  return
m = ans
for i in range(N-K):
  d,t = ls.pop()
  if t in S:
    continue
  S.add(t)
  m -=pre.pop()
  m += d+2*num+1
  num += 1
  ans = max(ans,m)
  if pre==[]:
    break
print(ans)

n,k=map(int,input().split())
from operator import itemgetter as it
l=sorted([list(map(int,input().split()))for i in range(n)],reverse=1,key=it(1))
from collections import defaultdict
c=defaultdict(int)
from heapq import heapify, heappop, heappush
now=[]
S=0
kind=0
for i in range(k):
    a,s=l[i]
    S+=s
    c[a]+=1
    if c[a]>1:heappush(now,(s,a))
    kind+=c[a]==1
ans=S+kind**2
for i in range(k,n):
    if not now:break
    x,y=l[i]
    if c[x]:continue
    s,a=heappop(now)
    c[x]+=1
    kind+=1
    S+=y-s
    ans=max(ans,S+kind**2)
print(ans)

def main():
    N, K = list(map(int, input().split()))
    TD = [tuple(map(int, input().split())) for _ in range(N)]
    TD.sort(key=lambda x: x[1], reverse=True)
    s = set()
    rep = []
    for t, d in TD[:K]:
        if t in s:
            rep.append(d)
        else:
            s.add(t)
    m = sum(d for _, d in TD[:K])
    p = len(s) ** 2 + m
    for t, d in TD[K:]:
        if not rep:
            break
        if t in s:
            continue
        m += d - rep.pop()
        s.add(t)
        p = max(p, len(s) ** 2 + m)
    return p

print((main()))


import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = 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)

import heapq

from typing import List


def main():
    n, k = list(map(int, input().split()))
    v = []
    for _ in range(n):
        t, d = list(map(int, input().split()))
        v.append((t, d))

    print((vs(v, k)))


def vs(v: List[List[int]], k: int) -> int:
    v.sort(key=lambda x: x[1], reverse=True)

    # Dup type
    h0 = []
    # New type
    h1 = []
    # types
    s = set()
    types = 0
    op = 0

    for i in range(k):
        t, d = v[i]
        op += d

        if t in s:
            heapq.heappush(h0, d)
            continue

        types += 1
        s.add(t)

    for i in range(k, len(v)):
        t, d = v[i]

        if not t in s:
            s.add(t)
            heapq.heappush(h1, -d)

    result = op + types ** 2

    while len(h0) > 0 and len(h1) > 0:
        d0 = heapq.heappop(h0)
        d1 = -heapq.heappop(h1)
        op = op - d0 + d1
        types += 1
        tmp = op + types ** 2

        if tmp > result:
            result = tmp

    return result


def __starting_point():
    main()

__starting_point()

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# x * xをどう評価するか、heapに「おいしさ」の高い順に入れていく
N, K = lr()
TD = [lr() for _ in range(N)]
heap = []
kind = 0
happy = 0
used = set()
TD.sort(key=lambda x: x[1], reverse=True)
for t, d in TD[:K]:
    if t not in used:
        used.add(t)
        kind += 1
    else:
        heappush(heap, d)
    happy += d

cand = [happy+kind**2]
for t, d in TD[K:]:
    if not heap:
        break
    if t in used:
        continue
    h = heappop(heap)
    happy += (d-h)
    kind += 1
    used.add(t)
    cand.append(happy+kind**2)

answer = max(cand)
print(answer)


import heapq

N, K = list(map(int, input().split()))
sushi = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1], reverse=True)

eaten = [False]*N

#d1: 種類が増えないもの同士、d2: 同じ種類の中で最大の組み合わせ
d1, d2 = [0], [0]

for i in range(N):
    t, d = sushi[i]
    t -= 1
    if eaten[t]:
        d1.append(d1[-1]+d)
    else:
        eaten[t] = True
        d2.append(d2[-1]+d)


ans = 0
for i in range(1, K+1):
    if K-i >= len(d1):
        continue
    if i >= len(d2):
        continue
    ans = max(ans, d1[K-i]+d2[i]+i**2)
print(ans)


import heapq
N,K = list(map(int,input().split()))

L = [[] for _ in range(N)]
All = []
s = set([])
for i in range(N):
  t,d = list(map(int,input().split()))
  t-=1 #0スタートに
  heapq.heappush(L[t], -d) #最大から取り出したいので負にする。
  heapq.heappush(All,[-d,t]) #すべてから大きい順に取り出せるように 
  s.add(t)

#print(L,s)
point = 0
ns = 0 #現在の種類
later = []
now = []
syurui = set([])
while len(now) < K and All:
  temp = heapq.heappop(All)
  if temp[1] not in syurui:
    ns += 1
    point -= temp[0]
    syurui.add(temp[1])
    heapq.heappush(now, -1*temp[0])
  else:
    later.append(temp)
for i in later:
  heapq.heappush(All,i)

point += ns*ns
while len(now) < K:
  temp = heapq.heappop(All)
  point -= temp[0]
  heapq.heappush(now, -1*temp[0])

#print(ns,point)
#print(now,All,All[0][0])
while All and now[0] < -1*All[0][0]:
  temp = heapq.heappop(All)
  dele = heapq.heappop(now)
  #print(temp,dele)
  upoint = point - temp[0] - dele - ns*ns + (ns-1)**2
  #print(upoint,point)
  if upoint >= point:
    point = upoint
    ns -= 1
  else:
    break
    
print(point)
#print(All)
#print(now)


import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = []
    for _ in range(N):
        t, d = map(int, input().split())
        S.append((d, t))
    S.sort(reverse = True)
    upperKCount = 0
    appeared = set()
    maxPoint = 0
    for i in range(K):
        maxPoint += S[i][0]
        if S[i][1] not in appeared:
            upperKCount += 1
            appeared |= {S[i][1]}
    maxPoint += upperKCount ** 2
    appeared = set()

    typeMax = []
    typeNum = 0
    typeLower = []
    others = 0
    for d, t in S:
        if t in appeared: 
            typeLower.append(d)
            others += 1
        else:
            typeMax.append(d)
            typeNum += 1
            appeared |= {t}
    typeMaxSum = [0] * (typeNum + 1)
    typeLowerSum = [0] * (others + 1)
    for i in range(typeNum): typeMaxSum[i+1] = typeMaxSum[i] + typeMax[i]
    for i in range(others): typeLowerSum[i+1] = typeLowerSum[i] + typeLower[i]
    for k in range(upperKCount + 1, min(typeNum, K) + 1):
        maxPoint = max(maxPoint, k ** 2 + typeMaxSum[k] + typeLowerSum[K - k])
    print(maxPoint)
    return 0

def __starting_point():
    solve()
__starting_point()

import sys
sys.setrecursionlimit(100000000)

def main():
    N,K = map(int,input().split())
    sushi = [tuple(map(int,input().split())) for _ in range(N)]

    sushi.sort(key = lambda x:x[1],reverse = True)
    ans = 0
    dic = {}
    change = []
    for a,b in sushi[:K]:
        if a in dic:
            dic[a].append(b)
            change.append((a,b))
        else:
            dic[a] = [b]
        ans += b

    various = len(dic)
    ans += various ** 2
    ret = ans
    used_type = set(dic.keys())
    suggestion = [p for p in sushi[K:] if p[0] not in used_type]
    for a,b in suggestion:
        if len(change) == 0:
            break
        if a in used_type:
            continue
        dic[change[-1][0]].pop()
        ret -= change[-1][1]
        ret += b + 2*various + 1
        dic[a] = b
        change.pop()
        various += 1
        used_type.add(a)
        ans = max(ans,ret)
    print(ans)
def __starting_point():
    main()
__starting_point()

from heapq import heappush,heappop
n,k = map(int,input().split())
kind_value = [[] for _ in range((n+1))]
for i in range(n):
    t,d = map(int,input().split())
    kind_value[t].append(d)
for li in kind_value:
    li.sort()
first_type = [(li[-1],i)for i,li in enumerate(kind_value) if li]
first_type.sort(reverse = True)
kind = 0
value_type1 = 0
second_type = []
second_type_sum = 0
second_type_cnt = 0

answer = 0
for v,i in first_type:
    kind += 1
    if kind > k:
        break
    value_type1 += v
    for d in kind_value[i][:-1]:
        heappush(second_type,d)
        second_type_sum += d
        second_type_cnt += 1
    while second_type_cnt > k-kind:
        d = heappop(second_type)
        second_type_cnt -= 1
        second_type_sum -= d
    value = kind*kind + value_type1 + second_type_sum
    if answer < value:
        answer = value

print(answer)

import sys
input=sys.stdin.readline
from heapq import heappop,heappush
hq=[]
n,k=list(map(int,input().split()))
for i in range(n):
	t,d=list(map(int,input().split()))
	heappush(hq,(-d,t))
D=0
dic={}
got=[]
for i in range(k):
	r=heappop(hq)
	got.append(r)
	if r[1] in dic:
		dic[r[1]]+=1
	else:
		dic[r[1]]=1
	D+=-r[0]
ans=D+len(dic)**2

while hq:
	while got:
		p=got.pop()
		if dic[p[1]]>1:
			dic[p[1]]-=1
			D-=-p[0]
			break
	if len(got)==0:
		print(ans)
		return

	r=heappop(hq)
	got.append(r)
	if r[1] in dic:
		dic[r[1]]+=1
	else:
		dic[r[1]]=1
	D+=-r[0]	
	ans=max(D+len(dic)**2,ans)
print(ans)


import heapq
N,K = list(map(int, input().split()))

I = []
for _ in range(N):
  t,d = list(map(int, input().split()))
  I.append((d,t))
  
I.sort(reverse=True)

# heap_can_delete
h_d = []
# heap_can_add
h_a = []

wk = 0
kind = 0
# 出現したことのあるネタ
ap = set()
for i in range(K):
  d,t = I[i]
  wk += d
  if t not in ap:
    ap.add(t)
    kind += 1
  else:
    heapq.heappush(h_d, (d,t))

for i in range(K,N):
  d,t = I[i]
  if t not in ap:
    ap.add(t)
    # maxをpopさせるために、価値を-1かけておく
    heapq.heappush(h_a, ((-1) * d, t))
  
ans = wk + kind ** 2
while len(h_d) > 0 and len(h_a) > 0:
  d1,t1 = heapq.heappop(h_d)
  d2,t2 = heapq.heappop(h_a)
  d2 = (-1) * d2
  wk = wk - d1 + d2
  kind += 1
  ans = max(ans, wk + kind ** 2)
  
print(ans)
  


import heapq
from collections import Counter
inf = 10**10
n, k = map(int, input().split())

dset = [[] for i in range(n)]
for i in range(n):
    t, d = map(int, input().split())
    dset[t-1].append(d)

for dd in dset:
    if dd: dd.sort(reverse=True)
    else: dd.append(-inf)

dset.sort(key= lambda x: -x[0])

cur = 0
hq = []
# k種類の先頭を除いて格納
for i in range(k):
    cur+=dset[i][0]
    for d in dset[i][1:]: heapq.heappush(hq, -d)

# 残りの種類のすべてを格納
for dd in dset[k:]:
    for d in dd:
        heapq.heappush(hq, -d)

ans = cur + k*k
for i in range(k-1, -1, -1):
    v = dset[i][0] # 削除候補
    if hq:
        w = -heapq.heappop(hq)
    else:
        break
    if v < w:
        cur += w - v
        # heapq.heappush(hq, -v)
    else:
        heapq.heappush(hq, -w)
    ans = max(ans, cur + i*i)
print(ans)

from heapq import heappush, heappop


N, K, *td = list(map(int, open(0).read().split()))
sushis = [(d, t) for t, d in zip(*[iter(td)] * 2)]
sushis.sort(reverse=True)

pq = []
cnt = [0] * (N + 1)
base, x = 0, 0
for d, t in sushis[:K]:
    base += d
    if cnt[t] > 0:
        heappush(pq, (d, t))
    elif cnt[t] == 0:
        x += 1
    cnt[t] += 1
ans = base + x * x

for d, t in sushis[K:]:
    if not pq:
        break
    if cnt[t] > 0:
        continue

    _d, _t = heappop(pq)
    cnt[_t] -= 1
    cnt[t] += 1
    x += 1
    base += d - _d
    ans = max(ans, base + x * x)

print(ans)


from collections import defaultdict
from heapq import heappush, heappop
N,K,*L = map(int, open(0).read().split())
dic = defaultdict(list)
ls = []
for i,(t,d) in enumerate(zip(*[iter(L)]*2)):
  dic[t].append(d)
  heappush(ls,(-d,t))
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
  d,t = heappop(ls)
  ans -= d
  if t not in S:
    num += 1
    S.add(t)
  else:
    heappush(pre,-d)

ans += num*num
if pre==[]:
  print(ans)
  return
m = ans
for i in range(N-K):
  d,t = heappop(ls)
  if t in S:
    continue
  S.add(t)
  m -= heappop(pre)
  m += -d+2*num+1
  num += 1
  ans = max(ans,m)
  if pre==[]:
    break
print(ans)

# 種類が同じ寿司であれば、最も美味しさが高い寿司を選ぶべき。
# 従い、
# (1)各種類の最も美味しさが高い寿司グループ
# (2)それ以外の寿司グループ
# をいずれも降順に並べて、(1)から幾つ取るか(最低でも1つは取る)を全探索する
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())

from collections import defaultdict
sushi = defaultdict(list) # 種類・おいしさ　のdictionary

for i in range(N):
  t,d = map(int,readline().split())
  sushi[t].append(d)
  
best_sushi = []
other_sushi = []

for value in sushi.values():
  value = sorted(value, reverse = True)
  best_sushi.append(value[0])
  other_sushi += value[1:]

best_sushi = sorted(best_sushi, reverse = True)
other_sushi = sorted(other_sushi, reverse = True)

best_num = 1 # best_sushiから選ぶ個数
other_num = K - 1 # other_sushiから選ぶ個数

if len(other_sushi) < other_num: # 選べない場合
  other_num = len(other_sushi)
  best_num = K - other_num
  
# それぞれの寿司から選ぶ個数の開始値が決定
# other_sushiの後ろの要素は切り離して良い

other_sushi = other_sushi[:other_num]
  
sushi_point = sum(best_sushi[:best_num]) + sum(other_sushi)
kind_point = best_num ** 2

ans = sushi_point + kind_point

# best寿司のインデックスを進めていく
for i in range(best_num, len(best_sushi)):
  sushi_point += best_sushi[i]
  if len(other_sushi) == 0:
    break
  rem = other_sushi.pop() # 取り除く寿司
  sushi_point -= rem
  kind_point = (i + 1) ** 2
  
  if ans < sushi_point + kind_point:
    ans = sushi_point + kind_point
    
print(ans)

def main():
    from heapq import heappush, heappop
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

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

    dd = []
    for _ in range(N):
        t, d = list(map(int, input().split()))
        t -= 1
        dd.append((d, t))
    dd.sort(key=itemgetter(0), reverse=True)

    ret = 0
    biggest = [-1] * N
    h = []
    kinds = 0
    for d, t in dd[:K]:
        ret += d
        if ~biggest[t]:
            if biggest[t] > d:
                heappush(h, d)
            else:
                heappush(h, biggest[t])
                biggest[t] = d
        else:
            kinds += 1
            ret += kinds * 2 - 1
            biggest[t] = d

    ans = ret
    for d, t in dd[K:]:
        if ~biggest[t]: continue
        if not h: break
        kinds += 1
        diff = d + kinds * 2 - 1 - h[0]
        ret += diff
        if ans < ret: ans = ret
        biggest[t] = d
        heappop(h)

    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import Counter

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

TD.sort(reverse=True, key=lambda a: a[1])

A = TD[:K]

B = []
V = set()
for t, d in TD:
    if t in V:
        continue
    B.append((t, d))
    V.add(t)

cntT = Counter([t for t, _ in A])
V = set(cntT.keys())
S = sum([d for _, d in A])
B = [(t, d) for t, d in B if not t in V]

C = []
for t, d in A[::-1]:
    if cntT[t] > 1:
        C.append((t, d))
        cntT[t] -= 1

C = C[::-1]
ans = S + len(V)**2
for t, d in B:
    if not C:
        break
    _, less = C.pop()
    S -= less
    S += d
    V.add(t)
    ans = max(ans, S + len(V)**2)
print(ans)


N,K,*L=list(map(int,open(0).read().split()))
S=sorted([(d,t)for t,d in zip(*[iter(L)]*2)],reverse=True)
In=set()
C=X=0
uni=[]
dub=[]
for d,t in S:
	if t not in In:
		In.add(t)
		uni.append(d)
		X+=1
		if X==K:
			break
	else:
		dub.append(d)
det=0
C=X
for d in dub:
	if C<K:
		det+=d
		C+=1
	elif uni[-1]+2*X-1<=d:
		uni.pop()
		X-=1
		det+=d
print((sum(uni)+det+X**2))



# 解説見て書く

N, K = [int(x) for x in input().split()]
td = [0] * (N)
for i in range(N):
    td[i] = [int(x) for x in input().split()]

# ネタ種類降順でソート
# 同じネタの中ではおいしいものから順に並ぶ
td = sorted(td, reverse = True)

var_p1 = [0] * N   # 種類数を増やす寿司のリスト
var_p0 = [0] * N   # 種類数を増やさない寿司のリスト

n_p1 = 0
n_p0 = 0
for i in range(N):
    if i == 0 or (i > 0 and td[i][0] != td[i - 1][0]):  # 種類が変わる
        var_p1[n_p1] = td[i][1]  # おいしさを追加
        n_p1 += 1
    else:
        var_p0[n_p0] = td[i][1]  # おいしさを追加
        n_p0 += 1

var_p1.sort(reverse = True)
var_p0.sort(reverse = True)

val_taste = sum(var_p0[0 : K])
val_vars = 0
ans = 0

for j in range(1, K + 1):  # 種類数1〜Kを試す
    val = var_p1[j - 1]
    if val <= 0: break  # これ以上種類を増やせない
    # var_p1からn_p1個選び、var_p0からK - n_p1個選ぶ
    val_taste = val_taste + val - var_p0[K - j]
    val_vars = j * j
    ans = max(ans, val_taste + val_vars)

print(ans)

n,k = list(map(int,input().split()))
s = set()
l = []
ln = [[] for i in range(n)]
for i in range(n):
    t,m = list(map(int,input().split()))
    l.append([m,t-1])
    ln[t-1].append(m)
l.sort(reverse = True)
cand = []

ans = 0
mod = []
for i in range(k):
    ans += l[i][0]
    if l[i][1] in s:
        mod.append(l[i][0])
    else:
        s.add(l[i][1])
x = len(s)
now = ans + x**2

for i in range(n):
    
    if i in s or ln[i] == []:
        continue
    cand.append(max(ln[i]))

cand.sort(reverse = True)

for i in range(min(len(mod),len(cand))):
    ans += cand[i]-mod[-1-i]
    x += 1
    now = max(now,ans+x**2)
print(now)





import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
nums = [[] for i in range(N)]
for i in range(N):
    t, d = list(map(int, input().split()))
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    if len(nums[i]) == 0: continue
    nums[i].sort(reverse=True)
    maxs.append(nums[i][0])
    for n in nums[i][1:]:
        rest.append(n)
maxs.sort(reverse=True)
rest.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)


import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = 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)

# 種類が同じ寿司であれば、最も美味しさが高い寿司を選ぶべき。
# 従い、
# (1)各種類の最も美味しさが高い寿司グループ
# (2)それ以外の寿司グループ
# をいずれも降順に並べて、(1)から幾つ取るか(最低でも1つは取る)を全探索する
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())

from collections import defaultdict
sushi = defaultdict(list) # 種類・おいしさ　のdictionary

for i in range(N):
  t,d = map(int,readline().split())
  sushi[t].append(d)
  
best_sushi = []
other_sushi = []

for value in sushi.values():
  value = sorted(value, reverse = True)
  best_sushi.append(value[0])
  other_sushi += value[1:]

best_sushi = sorted(best_sushi, reverse = True)
other_sushi = sorted(other_sushi, reverse = True)

#print("best_sushi",best_sushi)
#print("other_sushi",other_sushi)

best_num = 1 # best_sushiから選ぶ個数
other_num = K - 1 # other_sushiから選ぶ個数

if len(other_sushi) < other_num: # 選べない場合
  other_num = len(other_sushi)
  best_num = K - other_num
  
# それぞれの寿司から選ぶ個数の開始値が決定
# other_sushiの後ろの要素は切り離して良い

other_sushi = other_sushi[:other_num]
  
sushi_point = sum(best_sushi[:best_num]) + sum(other_sushi)
kind_point = best_num ** 2

ans = sushi_point + kind_point
#print("初期値",ans,"sum(best_sushi[:best_num])",sum(best_sushi[:best_num]),"sum(other_sushi)",sum(other_sushi),"best_num ** 2",best_num ** 2)

# best寿司のインデックスを進めていく
for i in range(best_num, len(best_sushi)):
  sushi_point += best_sushi[i]
  #print("----best_sushi[i]",best_sushi[i],"を追加")
  if len(other_sushi) == 0:
    break
  rem = other_sushi.pop() # 取り除く寿司
  sushi_point -= rem
  kind_point = (i + 1) ** 2
  
  #print("sushi_point",sushi_point,"kind_point",kind_point,"合計",sushi_point + kind_point)
  
  if ans < sushi_point + kind_point:
    ans = sushi_point + kind_point
    
print(ans)

import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
nums = []
for i in range(N):
    t, d = list(map(int, input().split()))
    nums.append((d, t))
nums.sort(reverse=True)
se = set()
doubled = []
rest = []
points = 0
for i, n in enumerate(nums):
    if i < K:
        if not n[1] in se:
            se.add(n[1])
        else:
            doubled.append(n)
        points += n[0]
    else:
        rest.append(n)
ans = points + pow(len(se), 2)
idx = len(doubled)-1
for d, t in rest:
    if idx < 0: break
    if t in se: continue
    points -= doubled[idx][0]
    idx -= 1
    points += d
    se.add(t)
    ans = max(ans, points+pow(len(se), 2))
print(ans)


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    td = [list(map(int, input().split())) for _ in range(n)]
    td.sort(reverse=True, key=lambda a: a[1])
    delicious = 0
    syurui = set()
    suteru = []
    for i in range(k):
        t, d = td[i]
        delicious += d
        if  t in syurui:
            suteru.append(d)
        else:
            syurui.add(t)
    #heapify(suteru)
    suteru.sort()
    neta = len(syurui)
    res = delicious + neta**2
    for i in range(k, n):
        t, d = td[i]
        if t in syurui:
            continue
        if len(suteru)==0:
            print(res)
            return
        syurui.add(t)
        x = suteru.pop(0)
        delicious += d - x
        neta += 1
        res = max(res, delicious+neta**2)
    print(res)

def __starting_point():
    main()
__starting_point()


n, k = list(map(int, input().split()))
sushi = []
for i in range(n):
    sushi.append(list(map(int, input().split())))
point = 0
sushi_kind = set()
duplication = []
sushi.sort(key=lambda x: x[1],reverse = True)
for i in range(k):
    point += sushi[i][1]
    if sushi[i][0] in sushi_kind:
        duplication.append(sushi[i])
    else:
        sushi_kind.add(sushi[i][0])
ans = point + pow(len(sushi_kind),2)
dup_index = len(duplication) - 1
for i in range(k,n):
    if sushi[i][0] in sushi_kind:
        continue
    else:
        if dup_index >= 0:
            point -= duplication[dup_index][1]
            dup_index -= 1
            point += sushi[i][1]
            sushi_kind.add(sushi[i][0])
    ans = max(ans, point + pow(len(sushi_kind),2))
print(ans)



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)



# -*-coding: utf-8 -*-

import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(n)]
    S.sort(key=lambda x: -x[1])
    y_1, y_0 = [0], [0]
    st = set()

    for t, d in S:
        if t in st:
            #累積報酬和のリスト
            y_0.append(y_0[-1]+d)
        else:
            st.add(t)
            y_1.append(y_1[-1]+d)
    

    max_sum = -1

    for i in range(1,k+1):
        if k-i >= len(y_0):
            continue
        if i >= len(y_1):
            break
        max_sum = max(max_sum, y_0[k-i]+y_1[i]+i**2)
    
    print(max_sum)
    return


def __starting_point():
    main()
__starting_point()

import sys
from collections import deque
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = list(map(int, input().split()))
    TD = [list(map(int, input().split())) for _ in range(n)]
    TD.sort(key=lambda z: -z[1])
    TD_new = [[] for _ in range(n)]
    for t, d in TD:
        TD_new[t - 1].append([d, 0] if len(TD_new[t - 1]) else [d, 1])

    ALL = []
    for td in TD_new:
        ALL.extend(td)
    ALL.sort(reverse=True)
    que = deque(ALL)

    x = y = 0
    zero = []
    for _ in range(k):
        d, ex = que.popleft()
        x += d
        y += ex
        if ex == 0:
            heappush(zero, d)

    res = x + y ** 2
    while que:
        d, ex = que.popleft()
        if ex:
            if zero:
                x += d - heappop(zero)
                y += 1
                res = max(res, x + y ** 2)
            else:
                break

    print(res)


def __starting_point():
    resolve()

__starting_point()

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)
cand = []
memo = [0 for i in range(n+1)]

ans = 0
duplicate = []
unique = []
num = 0
i = 0

for t, d in td:
    i += 1
    if i <= k:
        ans += d
        if memo[t]:
            duplicate.append(d)
        else:
            memo[t] = 1
            num += 1
    else:
        if not memo[t]:
            unique.append(d)
            memo[t] = 1

tmp = ans
ans += num * num

# print(tmp, ans)

for d, u in zip(reversed(duplicate), unique):
    tmp += u - d
    num += 1
    ans = max(ans, tmp + num * num)

print(ans)


n,k=list(map(int,input().split()))
top=[0]*n
sub=[]
for _ in range(n):
    t,d=list(map(int,input().split()))
    t-=1
    if top[t]==0:
        top[t]=d
    else:
        if d>top[t]:
            sub.append(top[t])
            top[t]=d
        else:
            sub.append(d)
top.sort(reverse=True)
top_sum=[0]
sub.sort(reverse=True)
sub_sum=[0]

for i in top:
    if i==0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1]+i)
for i in sub:
    sub_sum.append(sub_sum[-1]+i)
ans=0
for i in range(1,k+1):
    if i+len(sub_sum)-1>=k and top_sum[i]!=-1:
        ans=max(ans,top_sum[i]+sub_sum[k-i]+i**2)
print(ans)



# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
TD = [tuple(map(int,input().split())) for _ in range(N)]

# 美味しい順にソートしておく
#  t : ネタの種類
#  d : 美味しさ基礎ポイント
TD.sort(key=lambda x:x[1], reverse=True)

# 美味しい順にK個食べた場合の満足ポイント
ans = 0
s = set() # 食べたネタの集合
r = list() # すでに食べたネタ, あとで交換する用
for i in range(K):
    t,d = TD[i]
    ans += d
    if t not in s:
        s.add(t) # 食べたネタの種類の集合
    else:
        r.append(TD[i])
ans += len(s)**2

Ans = ans

# 美味しい順のK+1番目から, ネタの種類が増えるような操作を順番に試していく
for i in range(K,N):
    t0,d0 = TD[i]
    # まだ食べてないネタ and 交換用の寿司があるなら
    if t0 not in s and len(r) > 0:
        # 交換用の寿司の一番美味しさ基礎ポイントが低いものを交換するのが最善
        t1,d1 = r.pop()
        # 満足ポイントの再計算
        ans = ans - d1 + d0 - len(s)**2 + (len(s)+1)**2
        # 食べたネタの集合に追加
        s.add(t0)
        # 満足度が大きくなったか都度確認
        Ans = max(Ans,ans)

print(Ans)

# tokenakatta ...
def main():
    N, K = list(map(int, input().split()))
    l = []
    for _ in range(N):
        t, d = list(map(int, input().split()))
        l.append((t, d))
    l.sort(key=lambda x:x[1], reverse=True)
    s = set()
    e = []
    t = 0
    for i in range(K):
        t += l[i][1]
        if l[i][0] in s:
            e.append(l[i])
        else:
            s.add(l[i][0])
    rl = [t + len(s) * len(s)]
    e.reverse()
    ei = 0
    for i in range(K, N):
        if l[i][0] in s:
            continue
        if ei >= len(e):
            break
        s.add(l[i][0])
        t -= e[ei][1]
        t += l[i][1]
        ei += 1
        rl.append(t + len(s) * len(s))
    return max(rl)
print((main()))


n,k=map(int,input().split())
INF=10**18
sushi=[[-INF] for _ in range(n)]
for _ in range(n):
  t,d=map(int,input().split())
  sushi[t-1].append(d)
for i in range(n):
  sushi[i].sort(reverse=True)
sushi.sort(key=lambda x:x[0],reverse=True)
q=[]
res=0
for i in range(k):
  res+=sushi[i][0]
  for j in sushi[i][1:]:
    q.append(j)
q.sort()
cur=res
res+=k**2
for var in range(1,k)[::-1]:
  a=q.pop()
  b=sushi[var][0]
  cur+=a-b
  res=max(res,cur+var**2)
print(res)

def main():
    n, k = map(int, input().split())
    sushi = [list(map(int, input().split())) for _ in range(n)]
    sushi.sort(key=lambda x: x[1], reverse=True)
    ans = 0
    t = [0]*(n+1)
    tmp = 0
    cnt = 0
    for i in range(k):
        ans += sushi[i][1]
        if t[sushi[i][0]] == 0:
            cnt += 1
        tmp += sushi[i][1]
        t[sushi[i][0]] += 1
    ans = tmp + cnt*cnt
    p = k
    for i in range(k, n):
        f = False
        if t[sushi[i][0]] == 0:
            f = True
            for j in reversed(range(p)):
                if 1 < t[sushi[j][0]]:
                    t[sushi[j][0]] -= 1
                    t[sushi[i][0]] += 1
                    tmp -= sushi[j][1]
                    tmp += sushi[i][1]
                    p = j
                    cnt += 1
                    ans = max(ans, tmp+cnt*cnt)
                    f = False
                    break
        if f:
            break
    print(ans)


def __starting_point():
    main()
__starting_point()

N, K = map(int, input().split())
S = [tuple(map(int, input().split())) for _ in range(N)]

S.sort(key=lambda x: -x[1])
st = set()
first_acc, other_acc = [0], [0]
for t, d in S:
  if t in st:
    other_acc.append(other_acc[-1] + d)
  else:
    st.add(t)
    first_acc.append(first_acc[-1] + d)

ans = 0
for i in range(K + 1):
  if len(first_acc) <= i or len(other_acc) <= K - i:
    continue
  ans = max(ans, first_acc[i] + other_acc[K - i] + i * i)

print(ans)

# 写経AC

from heapq import heappop,heappush

INF = 10 ** 18

N, K = map(int, input().split())
# S[i]: 種類iの美味しさの集合
S = [[] for _ in range(N)]
for _ in range(N):
    t,d = map(int, input().split())
    S[t-1].append(d)

# 各種類について、美味しい順に並べる
for i in range(N):
    S[i].sort(reverse = True)
    if not S[i]: S[i].append(-INF) # 番兵

# 「美味しさの最大値」の降順でソート
S.sort(reverse = True)

uma = 0 # おいしさ基礎ポイント
que = [] # 選ばれていない寿司の美味しさリスト
for i in range(K):
    # ある種類の一番美味しい寿司を選ぶ
    uma += S[i][0]
    for j in range(1, len(S[i])):
        heappush(que, (-1) * S[i][j])

# 残りの寿司もリストに追加
for i in range(K, N):
    for j in range(len(S[i])):
        heappush(que, (-1) * S[i][j])

ans = uma + K * K
# 種類を減らしていく
for x in range(K - 1, 0, -1):
    v = S[x][0] # 選ばれている最小の「おいしさ」
    w = (-1) * que[0] # 選ばれていない最大の「おいしさ」
    if v < w:
        heappop(que)
        heappush(que, (-1) * v)
        uma -= v; uma += w
    ans = max(ans, uma + x * x)

print(ans)

from collections import defaultdict
N,K=map(int,input().split())

dtlist=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  dtlist.append((d,t))
  tset_all.add(t)
dtlist.sort()
#print(heapq)

dtlist_Krev=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  d,t=dtlist.pop()
  dtlist_Krev.append((d,t))
  dsum+=d
  tdic[t]+=1
#dtlist_Krev.sort(reverse=True)

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,min(K,len(tset_all))+1):
  while(True):    
    d1,t1=dtlist_Krev.pop()
    if tdic[t1]>1:
      tdic[t1]-=1
      dsum-=d1
      break
      
  while(True):        
    d2,t2=dtlist.pop()
    if tdic[t2]==0:
      tdic[t2]=1
      dsum+=d2      
      break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)

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)


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])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)


import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = [None] * N
    for i in range(N):
        t, d = map(int, input().split())
        S[i] = (-d, t)
    heapify(S)

    base_point = 0
    appeared_type = set()
    type_Num = 0
    duplicated = []
    heapify(duplicated)
    for i in range(K):
        d, t = heappop(S)
        if t in appeared_type:
            base_point -= d
            heappush(duplicated, -d)
        else:
            base_point -= d
            appeared_type |= {t}
            type_Num += 1

    Ans = base_point + type_Num * type_Num
    while S:
        d, t = heappop(S)
        if t in appeared_type: continue
        else:
            if not duplicated: continue
            else:
                remove = heappop(duplicated)
                base_point -= d + remove
                type_Num += 1
                appeared_type |= {t}
                Ans = max(Ans, base_point + type_Num * type_Num)
    print(Ans)

    return 0

def __starting_point():
    solve()
__starting_point()

import sys
input = sys.stdin.readline


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

SUSHI = []
for _ in range(n):
    t, d = list(map(int, input().split()))
    SUSHI.append((d, t))
SUSHI.sort(reverse = True)

NEW = {i:True for i in range(1, n + 1)}
x, y = 0, 0
A, B = [], []

for d, t in SUSHI[:k]:
    if NEW[t]:
        x += d; y += 1
        NEW[t] = False
    else:
        x += d
        A.append(d)

for d, t in SUSHI[k:]:
    if NEW[t]:
        B.append(d)
        NEW[t] = False
B.sort()

answer = x + y**2
while A and B:
    a, b = A.pop(), B.pop()
    x -= a; x += b; y += 1
    if x + y**2 > answer:
        answer = x + y**2

print(answer)


N,K=map(int,input().split())
sushi=[]
for i in range(N):
    t,d=map(int,input().split())
    sushi.append((t,d))
sushi.sort(key=lambda x:(x[0],-x[1]))
#print(sushi)
X=[sushi[0][1]]
Y=[]
for i in range(1,N):
    if sushi[i-1][0]==sushi[i][0]:
        Y.append(sushi[i][1])
    else:
        X.append(sushi[i][1])
X.sort(reverse=True)
Y.sort(reverse=True)
SX=[0]
SY=[0]
for i in X:
    SX.append(SX[-1]+i)
for i in Y:
    SY.append(SY[-1]+i)
ans=0
#print(X)
#print(Y)
#1<=x<len(X)
#K-len(Y)<=x<=
for x in range(max(1,K-len(Y)),min(len(SX),K+1)):
    ans=max(SX[x]+SY[K-x]+x*x,ans)
print(ans)

n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab_s = sorted(ab, key=lambda x: x[1])
ab_r = list(reversed(ab_s))

t = [x[0] for x in ab_r]
d = [x[1] for x in ab_r]        

t_set = len(set(t[:k]))
d_sum = sum(d[:k])

res = [t_set**2 + d_sum]

from collections import Counter
t_cou = Counter(t[:k])

dp =[0]*(n+1)
j_old = k-1

for i in t_cou:
    dp[i] = t_cou[i]

for i in range(k,n):
    t_new = ab_r[i][0]
    if dp[t_new] ==0:
        for j in range(j_old,-1,-1):
            t_old = ab_r[j][0]
            if dp[t_old] <=1:
                pass
            else:
                dp[t_new] =1
                dp[t_old] -=1
                t_set +=1
                d_sum = d_sum - ab_r[j][1] + ab_r[i][1]
                res.append(t_set**2 + d_sum)
                j_old = j-1
                break
            j_old = -1

print(max(res))