CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heappop, heappush, heapify

N, K = list(map(int, input().split()))
sushi = []
for _ in range(N):
    t, d = list(map(int, input().split()))
    sushi.append((-d, t))
heapify(sushi)

maxs = []
rems = []
kinds = set()
for _ in range(K):
    d, t = heappop(sushi)
    if t in kinds:
        heappush(rems, -d)
    else:
        maxs.append(-d)
        kinds.add(t)
ans = sum(maxs) + sum(rems) + len(kinds)**2

while True:
    if not sushi or not rems:
        break
    d, t = heappop(sushi)
    if t in kinds:
        continue
    else:
        heappop(rems)
        maxs.append(-d)
        kinds.add(t)
        ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)

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

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
# Original solution
n, k = list(map(int, input().split()))
nai = [list(map(int, input().split())) for _ in range(n)]

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

ans = 0
aru = []
spe = set()
m = 0

for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans+=anstmp[1]
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])

m = ans + sum(aru) + len(spe)**2

for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        aru.pop()
        ans+=nai[i][1]
        spe.add(nai[i][0])
    m = max(m, ans + sum(aru) + len(spe)**2)
print(m)


# Optimized solution
n, k = list(map(int, input().split()))
nai = [list(map(int, input().split())) for _ in range(n)]

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

ans = 0
aru = []
spe = set()
m = 0
for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans+=anstmp[1]
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])
sumaru = sum(aru)
m = ans + sumaru + len(spe)**2

for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        sumaru-=aru.pop()
        ans+=nai[i][1]
        spe.add(nai[i][0])
    m = max(m, ans + sumaru + len(spe)**2)
print(m)
# Original solution
from collections import *
n, k = list(map(int, input().split()))
d, t = list(zip(*sorted(tuple(map(int, input().split()))[::-1] for _ in range(n))[::-1]))
c = Counter(t[:k])
x = len(c)
a = [sum(d[:k])]
for i in range(k)[::-1]:
    if c[t[i]] > 1:
        c[t[i]] -= 1
        a.append(a[-1] - d[i])
b = [0]
for i in range(k, n):
    if c[t[i]] <= 0:
        c[t[i]] += 1
        b.append(b[-1] + d[i])
r = 0
for i, (v, w) in enumerate(zip(a, b)):
    r = max(r, v+w+(x+i)**2)
print(r)

# Optimized solution
n, k =list(map(int, input().split()))
dt = sorted(tuple(map(int, input().split()))[::-1] for _ in range(n))[::-1]
r = v = 0
a = []
s = set()
for i, (d,t) in enumerate(dt, 1):
    if t in s:
        if i <= k:
            a.append(d)
            v += d
    else:
        if i > k:
            if not a:
                break
            v -= a.pop()
        v += d
        s.add(t)
    r = max(r, len(s)**2+v)
print(r)
# Original solution
N,K = list(map(int,input().split()))
X = []
for i in range(N):
    t,d = list(map(int,input().split()))
    X.append((d,t))

X.sort(reverse=True)

p,v = 0,set([])
pp = []
for i in range(K):
    p += X[i][0]
    if X[i][1] not in v:
        v.add(X[i][1])
    else:
        pp.append((X[i][0],X[i][1]))

Ans = p + len(v)**2
ans = Ans
for i in range(K,N):
    if X[i][1] not in v and len(pp)>0:
        temp = pp[-1]
        pp = pp[:len(pp)-1]
        ans = ans - temp[0] + X[i][0] - len(v)**2 + (len(v)+1)**2
        v.add(X[i][1])
        Ans = max(Ans,ans)

print(Ans)


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

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


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = list(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)
# Original solution
N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

bucket = [0]*(N+1)
for t in n_dm_set:
    bucket[t] = -1

d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    t = t_arr[i]
    if bucket[t] != 0:
        continue
    d = d_arr[i]
    bucket[t] = d
    if len(small_arr) == 0:
        break
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)


# Optimized solution
N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)
# Original solution
import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])
    tl, dl = list(zip(*sl))

    gmk = set()
    ce = []
    for s in sl[:k]:
        if s[0] in gmk:
            ce.append(s)
        gmk.add(s[0])

    gop = sum(dl[:k])
    bmk = max(len(set(tl)), k)

    gscr = len(gmk)**2 + gop

    ce.sort(key=lambda x: x[1])
    for c in ce[:bmk-len(gmk)]:
        for s in sl[k:]:
            if s[0] in gmk:
                continue
            k += 1
            gmk.add(s[0])
            gop = gop - c[1] + s[1]
            nscr = len(gmk)**2 + gop
            gscr = max(gscr, nscr)
            break

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [list(map(int, input().split())) for _ in range(n)]
    print((r(n, k, sl)))


if __name__ == '__main__':
    main()


# Optimized solution
import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])

    gmk = set()
    gop = 0
    ce = []
    for ti, di in sl[:k]:
        if ti in gmk:
            ce.append(di)
        gmk.add(ti)
        gop += di

    gscr = len(gmk)**2 + gop

    for ti, di in sl[k:]:
        if 0 >= len(ce):
            break
        if ti in gmk:
            continue
        gmk.add(ti)
        odi = ce.pop()
        gop = gop - odi + di
        nscr = len(gmk)**2 + gop
        gscr = max(gscr, nscr)

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [tuple(map(int, input().split())) for _ in range(n)]
    print((r(n, k, sl)))


if __name__ == '__main__':
    main()
# Original solution
ri = lambda: int(eval(input()))
rl = lambda: list(map(int,input().split()))

N,K=rl()
td = [rl() for _ in range(N)]

from operator import itemgetter
key0 = itemgetter(0)
key1 = itemgetter(1)
td.sort(key=key1,reverse=True)

netas = set()
dup = []

for t,d in td[:K]:
    if t in netas:
        dup.append(d)
    else:
        netas.add(t)

score = len(netas)**2 + sum(map(key1,td[:K]))
ans = score
for t,d in td[K:]:
    if t not in netas and dup != []:
        netas.add(t)
        dup_ = dup.pop(-1)
        score += 2*len(netas)-1 + d - dup_
        ans = max(ans,score)
print(ans)

# Optimized solution
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 top[t]>=d:
            sub.append(d)
        else:
            sub.append(top[t])
            top[t]=d
 
top.sort()
top = top[::-1]
res = [0]
for i in range(n):
    if top[i]!=0:
        res.append(res[-1]+top[i])
    else:
        res.append(-1)
sub.sort()
sub = sub[::-1]
w = [0]
for i in range(len(sub)):
    w.append(w[-1]+sub[i])
tmp = 0
for i in range(1,k+1):
    if len(w)-1>=k-i and res[i]!=-1:
        tmp = max(res[i]+w[k-i]+i*i,tmp)
 
print(tmp)
# Original solution
# -*- coding: utf-8 -*-

def popMaxOishisa(sushis):
    t, d = sushis.pop()
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    if len(sel_sushis["min"]) == 0:
        return -1, -1
    t, d = min(list(sel_sushis["min"].items()), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"].pop(t)
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    t, d = -1, -1
    while True:
        t, d = sushis.pop()
        if not t in netas:
            break
    return t, d


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

# Store data
sushis = []
neta_set = set()
sel_sushis = {}
for i in range(n):
    t, d = list(map(int, input().split()))
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}
sel_neta = list(sel_sushis.keys())

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    if t1 < 0:
        break
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, sel_neta)
    sum_oishisa += d2

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)
    sel_neta.append(t2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)


# Optimized solution
# -*- coding: utf-8 -*-


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

# Store data
sushis = []
neta_set = set()
for i in range(n):
    t, d = list(map(int, input().split()))
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)


# Select sushi set as maximum oishisa point
sel_sushis = []
neta_set = set()
sum_oishisa = 0
for i in range(k):
    t, d = sushis.pop()
    if t in neta_set:
        sel_sushis.append((t,d))
    else:
        neta_set.add(t)
    sum_oishisa += d

sel_sushis.sort(key=lambda i:i[1], reverse=True)
tMin = len(neta_set)
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    if len(sel_sushis) == 0:
        break
    t1, d1 = sel_sushis.pop()
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    while True:
        t2, d2 = sushis.pop()
        if not t2 in neta_set:
            break

    sum_oishisa += d2
    neta_set.add(t2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)
# Original solution
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
td = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = []
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        heappush(q, d)
    else:
        v.append(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = heappop(q)
        cnt += d + 2 * len(v) + 1 - x
        v.append(t)
        ans = max(ans, cnt)
print(ans)


# Optimized solution
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
td = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = set()
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        heappush(q, d)
    else:
        v.add(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = heappop(q)
        cnt += d + 2 * len(v) + 1 - x
        v.add(t)
        ans = max(ans, cnt)
print(ans)
# Original solution
N, K = list(map(int, input().split()))
td = [list(map(int, input().split()))
      for _ in range(N)]
td.sort(key=lambda x: -x[1])
q = []
v = set()
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        q.append(d)
    else:
        v.add(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = q.pop()
        cnt += d + 2 * len(v) + 1 - x
        v.add(t)
        ans = max(ans, cnt)
print(ans)


# Optimized solution
N, K = list(map(int, input().split()))
td = [list(map(int, input().split()))
      for _ in range(N)]
td.sort(key=lambda x: -x[1])
q = []
v = set()
sd = 0
for t, d in td[:K]:
    sd += d
    if t in v:
        q.append(d)
    v.add(t)
ans = len(v) ** 2 + sd
for t, d in td[K:]:
    if 0 >= len(q):
        break
    if t in v:
        continue
    v.add(t)
    md = q.pop()
    sd = sd - md + d
    tans = len(v) ** 2 + sd
    ans = max(ans, tans)
print(ans)
# Original solution
from collections import defaultdict

n, k = list(map(int, input().split()))
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = defaultdict(int)
x = list(range(n - 1, n - k - 1, -1))
z = [0]
for i in range(n - k, n):
    t[sushi[i][0]] += 1
    z[0] += sushi[i][1]

y = []
yd = list(t.keys())
for i in range(n - k - 1, -1, -1):
    if sushi[i][0] not in yd:
        y.append(i)
        yd.append(sushi[i][0])
y = y[::-1]
k = 1

for k in range(1, len(y) + 1):
    for i in range(len(x) - 1, -1, -1):
        xi = x[i]
        if t[sushi[xi][0]] > 1:
            t[sushi[xi][0]] -= 1
            z.append(z[-1] - sushi[xi][1] + sushi[y[-k]][1])
            x.pop(i)
            break

p = len(list(t.keys()))
ans = 0
for i in range(len(z)):
    ans = max(ans, z[i] + (p + i) ** 2)
print(ans)


# Optimized solution
import heapq

n, k = list(map(int, input().split()))
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = 0
for i in range(n - 1, n - k - 1, -1):
    ti, di = sushi[i]
    if ti in list(t.keys()):
        heapq.heappush(x, di)
        t[ti] += 1
    else:
        t[ti] = 1
    z += di

p = len(list(t.keys()))
ans = z + p ** 2
for i in range(n - k - 1, -1, -1):
    if len(x) == 0:
        break
    ti, di = sushi[i]
    if ti not in list(t.keys()):
        t[ti] = 1
        z += di - heapq.heappop(x)
        p += 1
        ans = max(ans, z + p ** 2)

print(ans)
# Original solution
import sys, itertools
#def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
N, K = inpl()
Sushi = []
Neta = set()
ans = 0
for _ in range(N):
    t, d = inpl()
    Sushi.append((d, t))
Sushi.sort(reverse = True)
Db = []
Nd = []
for i in range(K):
    d, t = Sushi[i]
    if t not in Neta:
        Neta.add(t)
        ans += d
    else:
        Db.append(d)
neta = len(Neta)
Db = [0] + list(itertools.accumulate(Db))
Db.reverse()
for i in range(N-K):
    d, t = Sushi[K+i]
    if t not in Neta:
        Neta.add(t)
        Nd.append(d)
Nd = [0] + list(itertools.accumulate(Nd))
print((ans + max([(neta + i)**2 + j + k for i, (j, k) in enumerate(zip(Db, Nd))])))

# Optimized solution
import sys, itertools
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
N, K = inpl()
Sushi = []
Neta = set()
ans = 0
for _ in range(N):
    t, d = inpl()
    Sushi.append((d, t))
Sushi.sort(reverse = True)
Db = []
Nd = []
for i in range(K):
    d, t = Sushi[i]
    if t not in Neta:
        Neta.add(t)
        ans += d
    else:
        Db.append(d)
neta = len(Neta)
Db = [0] + list(itertools.accumulate(Db))
Db.reverse()
for i in range(N-K):
    d, t = Sushi[K+i]
    if t not in Neta:
        Neta.add(t)
        Nd.append(d)
Nd = [0] + list(itertools.accumulate(Nd))
print((ans + max([(neta + i)**2 + j + k for i, (j, k) in enumerate(zip(Db, Nd))])))
# Original solution
from collections import defaultdict
import heapq


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

sushi.sort(key=lambda x: x[1])
kinds = defaultdict(int)
eaten = []
ans = 0
for i in range(k):
    neta, point = sushi.pop()
    kinds[neta] += 1
    ans += point
    heapq.heappush(eaten, [point, neta])

num_of_kinds = len(list(kinds.keys()))
ans += num_of_kinds ** 2
candidate = ans

for i in range(k):
    point, neta = heapq.heappop(eaten)
    if kinds[neta] == 1:
        continue
    kinds[neta] -= 1

    while sushi:
        new_neta, new_point = sushi.pop()
        if kinds[new_neta] >= 1:
            continue
        else:
            break
    else:
        break
    kinds[new_neta] += 1
    num_of_kinds += 1
    delta = new_point - point + (2*num_of_kinds - 1)
    candidate += delta
    ans = max(ans, candidate)

print(ans)

# Optimized solution
from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline


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

sushi.sort(key=lambda x: x[1])
kinds = defaultdict(int)
eaten = []
ans = 0
for i in range(k):
    neta, point = sushi.pop()
    kinds[neta] += 1
    ans += point
    heapq.heappush(eaten, [point, neta])

num_of_kinds = len(list(kinds.keys()))
ans += num_of_kinds ** 2
candidate = ans

for i in range(k):
    point, neta = heapq.heappop(eaten)
    if kinds[neta] == 1:
        continue
    kinds[neta] -= 1

    while sushi:
        new_neta, new_point = sushi.pop()
        if kinds[new_neta] >= 1:
            continue
        else:
            break
    else:
        break
    kinds[new_neta] += 1
    num_of_kinds += 1
    delta = new_point - point + (2*num_of_kinds - 1)
    candidate += delta
    ans = max(ans, candidate)

print(ans)
# Original solution
N,K = list(map(int,input().split()))
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
ans = 0
sum_head = sum(head)
l_head = len(head)
l_no_head = len(no_head)
for i in range(n+1):
    ans = max(ans,sum_head+sum(no_head[:l_no_head-i])+sum(unused_head[:i]) + (l_head+i)**2)
print(ans)

# Optimized solution
N,K = list(map(int,input().split()))
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)
# Original solution
N,K = list(map(int,input().split()))
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)

# Optimized solution
N,K = list(map(int,input().split()))
TD = [list(map(int,input().split())) for _ in [0]*N]
TD.sort(key=lambda x:(-x[1],x[0]))
use = TD[:K]
var = set()
lock = []
unlock = []
for t,d in use:
    if t in var:
        unlock.append(d)
    else:
        var.add(t)
        lock.append(d)
unlock.sort(reverse=True)
Dscore = sum(lock) + sum(unlock)
v = len(var)
Vscore = v*v
ans = Dscore + Vscore
unused = TD[K:][::-1]
while unlock and unused:
    t,d = unused.pop()
    if t in var: continue
    trash = unlock.pop()
    var.add(t)
    lock.append(d)
    v += 1
    Dscore += d - trash
    Vscore = v*v
    ans = max(ans,Dscore + Vscore)
print(ans)