CodeEff/ECCO huggingface dataset:
# Original solution
def solve():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Sushi = namedtuple('Sushi', 'taste kind')

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

    e = []
    for _ in range(n):
        t, d = list(map(int, input().split()))
        e.append(Sushi(taste=d, kind=t - 1))

    e.sort(key=attrgetter('taste'), reverse=True)

    ret = 0
    used = [False] * n  # 選択されている種類
    q = deque()  # 選択から外す候補,[high->low]
    x = 0  # 暫定選択の種類数
    for s in e[:k]:  # 美味しさ降順k個
        if used[s.kind]:
            q.append(s)  # 同じ種類の2個目以降のみ交換候補になる
        else:
            used[s.kind] = True
            x += 1
        ret += s.taste
    ret += pow(x, 2)  # 種類ボーナス

    t = ret
    r = iter(e[k:])  # 交換で入れる候補
    while q:
        rem = q.pop()  # 選択から外す
        t -= rem.taste
        for s in r:
            if used[s.kind]:
                continue
            used[s.kind] = True
            t += s.taste + x * 2 + 1
            x += 1
            ret = max(ret, t)
            break
        else:
            break

    return ret


if __name__ == '__main__':
    print((solve()))

# k個持っておいて、下位を交換する


# Optimized solution
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)


if __name__ == '__main__':
    main()
# Original solution
from operator import itemgetter
from functools import reduce
N, K = list(map(int, input().split()))
t, d = list(zip(*(list(map(int, input().split())) for _ in range(N))))
fn = itemgetter(0)
fd = itemgetter(1)
ss = sorted(zip(t, d), key=fd, reverse=True)
netas = set()
duplicates = []
for s in ss[:K]:
  if s[0] in netas:
    duplicates.append(s[1])
  else:
    netas.add(s[0])
p = sum(map(fd, ss[:K])) + len(netas)**2
ans = p
for s in ss[K:]:
  if s[0] not in netas and duplicates:
    netas.add(s[0])
    duplicate = duplicates.pop()
    p += (s[1] - duplicate) + 2 * len(netas) - 1
    ans = max(ans, p)
print(ans)

# Optimized solution
from heapq import heappush, heappop

N, K = list(map(int, input().split()))
t, d = (
    list(zip(*(list(map(int, input().split())) for _ in range(N)))) if N else
    ((), ())
)

# おいしさについて貪欲に寿司を食べたときの満足ポイントを求める
# その後、種類ボーナスを1個ずつ増やしたときの満足ポイントをそれぞれ求め、
# それらの最大値を求める
S = sorted(zip(d, t), reverse=True)
q = []
v = set()
s = 0
for D, T in S[:K]:
    s += D
    if T in v:
        heappush(q, D)
    else:
        v.add(T)
s += len(v)**2
opt = s
for D, T in S[K:]:
    if T not in v and q:
        z = heappop(q)
        s += D + 2 * len(v) + 1 - z
        v.add(T)
        opt = max(opt, s)
ans = opt

print(ans)
# Original solution

import heapq


def main():
    num_sushi, chose_num = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(num_sushi)]

    data.sort(key=lambda x: -x[1])
    delicious_heap = []
    count_d, count_n = 0, 0
    neta_data = [0 for i in range(num_sushi + 1)]

    for i in range(chose_num):
        neta, oishisa = data[i]

        if neta_data[neta]:
            heapq.heappush(delicious_heap, oishisa)
        else:
            neta_data[neta] = 1
            count_n += 1

        count_d += oishisa

    ans = count_d + count_n ** 2

    for i in range(chose_num, num_sushi):
        if len(delicious_heap) == 0:
            break
        neta, oishisa = data[i]

        if neta_data[neta]:
            continue
        neta_data[neta] = 1
        count_n += 1
        pop_oishisa = heapq.heappop(delicious_heap)
        count_d += oishisa - pop_oishisa

        ans = max(ans, count_d + count_n ** 2)

    print(ans)


if __name__ == '__main__':
    main()

# Optimized solution

import heapq
import sys
input = sys.stdin.readline

def main():
    num_sushi, chose_num = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(num_sushi)]

    data.sort(key=lambda x: -x[1])
    delicious_heap = []
    count_d, count_n = 0, 0
    neta_data = [0 for i in range(num_sushi + 1)]

    for i in range(chose_num):
        neta, oishisa = data[i]

        if neta_data[neta]:
            heapq.heappush(delicious_heap, oishisa)
        else:
            neta_data[neta] = 1
            count_n += 1

        count_d += oishisa

    ans = count_d + count_n ** 2

    for i in range(chose_num, num_sushi):
        if len(delicious_heap) == 0:
            break
        neta, oishisa = data[i]

        if neta_data[neta]:
            continue
        neta_data[neta] = 1
        count_n += 1
        pop_oishisa = heapq.heappop(delicious_heap)
        count_d += oishisa - pop_oishisa

        ans = max(ans, count_d + count_n ** 2)

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
# -*- coding: utf-8 -*-

import sys
from heapq import heapify, heappush, heappop
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
DT = []
tmp = [[] for i in range(N)]
for i in range(N):
    t, d = MAP()
    DT.append((d, t))
DT.sort(reverse=1)

que = []
C = Counter()
dcnt = 0
# ポイント上位K個をまず取る
for i in range(K):
    d, t = DT[i]
    dcnt += d
    C[t] += 1
    heappush(que, (d, t))
heapify(que)
tcnt = len(C)

ans = dcnt + tcnt**2
for i in range(K, N):
    d2, t2 = DT[i]
    # 既に持っている種類ならスキップ
    if C[t2] > 0:
        continue
    tmp = []
    while que:
        d, t = heappop(que)
        # 2つ以上ある種類が来たら交換候補
        if C[t] >= 2:
            break
        else:
            tmp.append((d, t))
    # 全部1種類ずつになったらもう種類数を増やせないので終了
    if not que:
        break
    # この候補と交換してみる
    dcnt -= d
    dcnt += d2
    C[t] -= 1
    C[t2] += 1
    tcnt += 1
    ans = max(ans, dcnt + tcnt**2)
    # 今回使った分を含め、キューを元に戻す
    heappush(que, (d2, t2))
    for d, t in tmp:
        heappush(que, (d, t))
print(ans)


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

import sys
from heapq import heapify, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
DT = []
tmp = [[] for i in range(N)]
for i in range(N):
    t, d = MAP()
    DT.append((d, t))
DT.sort(reverse=1)

que = []
D = {}
dcnt = 0
# ポイント上位K個をまず取る
for i in range(K):
    d, t = DT[i]
    dcnt += d
    # 種類tが1つ目
    if t not in D:
        D[t] = d
    # 2つ目以降なら、最大のものはDに残して他はキューへ
    else:
        if D[t] < d:
            D[t], d = d, D[t]
        que.append((d, t))
heapify(que)
tcnt = len(D)

ans = dcnt + tcnt**2
for i in range(K, N):
    d2, t2 = DT[i]
    # 既に持っている種類ならスキップ
    if t2 in D:
        continue
    D[t2] = d2
    tmp = []
    # 全部1種類ずつならもう種類数を増やせないので終了
    if not que:
        break
    d, t = heappop(que)
    # この候補と交換してみる
    dcnt -= d
    dcnt += d2
    tcnt += 1
    ans = max(ans, dcnt + tcnt**2)
print(ans)
# Original solution
# -*- coding: utf-8 -*-

import sys
from heapq import heapify, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
DT = []
tmp = [[] for i in range(N)]
for i in range(N):
    t, d = MAP()
    DT.append((d, t))
DT.sort(reverse=1)

que = []
D = {}
dcnt = 0
# ポイント上位K個をまず取る
for i in range(K):
    d, t = DT[i]
    dcnt += d
    # 種類tが1つ目
    if t not in D:
        D[t] = d
    # 2つ目以降なら、最大のものはDに残して他はキューへ
    else:
        if D[t] < d:
            D[t], d = d, D[t]
        que.append((d, t))
heapify(que)
tcnt = len(D)

ans = dcnt + tcnt**2
for i in range(K, N):
    d2, t2 = DT[i]
    # 既に持っている種類ならスキップ
    if t2 in D:
        continue
    D[t2] = d2
    tmp = []
    # 全部1種類ずつならもう種類数を増やせないので終了
    if not que:
        break
    d, t = heappop(que)
    # この候補と交換してみる
    dcnt -= d
    dcnt += d2
    tcnt += 1
    ans = max(ans, dcnt + tcnt**2)
print(ans)


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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
DT = []
tmp = [[] for i in range(N)]
for i in range(N):
    t, d = MAP()
    DT.append((d, t))
DT.sort(reverse=1)

A = []
D = {}
dcnt = 0
# ポイント上位K個をまず取る
for i in range(K):
    d, t = DT[i]
    dcnt += d
    # 種類tが1つ目なら、確定で残す
    if t not in D:
        D[t] = d
    # 2つ目以降なら、最大のものを残して他は交換候補へ
    else:
        if D[t] < d:
            D[t], d = d, D[t]
        A.append(d)
A.sort(reverse=1)
tcnt = len(D)

ans = dcnt + tcnt**2
for i in range(K, N):
    d2, t2 = DT[i]
    # 既に持っている種類ならスキップ
    if t2 in D:
        continue
    D[t2] = d2
    # 全部1種類ずつ(交換候補がもうない)なら、もう種類数を増やせないので終了
    if not A:
        break
    d = A.pop()
    # この候補と交換してみる
    dcnt -= d
    dcnt += d2
    tcnt += 1
    ans = max(ans, dcnt + tcnt**2)
print(ans)
# Original solution
from operator import itemgetter

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

TD.sort(key=itemgetter(1), reverse=True)
selected = TD[:K]
dlc = sum(map(itemgetter(1), selected))
variety = set(map(itemgetter(0), selected))

used = set()
overlap = [] # ダブっているネタの美味しさのリスト
for t, d in TD[:K]:
    if t not in used:
        used.add(t)
    else:
        overlap.append(d)
answer = dlc + len(variety)**2

for t, d in TD[K:]:
    if not overlap:
        break
    if t in used:
        continue
    ov = overlap.pop()
    dlc = dlc - ov + d
    used.add(t)
    answer = max(answer, dlc + len(used)**2)

print(answer)


# Optimized solution
import sys

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

N, K = lr()
TD = [lr() for _ in range(N)]
TD.sort(key=lambda x: x[1], reverse=True)
used = set()
overlap = []
for t, d in TD[:K]:
    if t in used:
        overlap.append(d)
    else:
        used.add(t)

delicious = sum([x[1] for x in TD[:K]])
answer = delicious + len(used) ** 2
for i in range(K, N):
    if not overlap:
        break
    if TD[i][0] in used:
        continue
    delicious += (TD[i][1] -  overlap.pop())
    used.add(TD[i][0])
    if answer < delicious + len(used)**2:
        answer = delicious + len(used)**2

print(answer)
# 30
# Original solution
from heapq import heappush, heappop, heapreplace

INF = 10 ** 9 + 5

N, K, *TD = list(map(int, open(0).read().split()))

E = [[] for _ in range(N)]
for t, d in zip(*[iter(TD)] * 2):
    E[t - 1].append(d)

for e in E:
    if e:
        e.sort(reverse=True)
    else:
        e.append(-INF)
E.sort(key=lambda x: -x[0])

cur = 0
Q = []
for ei in E[:K]:
    cur += ei[0]
    for eij in ei[1:]:
        heappush(Q, -eij)

for ei in E[K:]:
    for eij in ei:
        heappush(Q, -eij)

res = cur + K * K
for x in reversed(list(range(1, K))):
    v, w = E[x][0], -Q[0]
    if v < w:
        heappop(Q)
        cur += w
        heappush(Q, -v)
        cur -= v

    res = max(res, cur + x * x)

print(res)


# Optimized solution
from heapq import heappush, heapreplace

def main():
    INF = 10 ** 9 + 5

    N, K, *TD = list(map(int, open(0).read().split()))

    E = [[] for _ in range(N)]
    for t, d in zip(*[iter(TD)] * 2):
        E[t - 1].append(d)

    for e in E:
        if e:
            e.sort(reverse=True)
        else:
            e.append(-INF)
    E.sort(key=lambda x: -x[0])

    cur = 0
    Q = []
    for ei in E[:K]:
        cur += ei[0]
        for eij in ei[1:]:
            heappush(Q, -eij)

    for ei in E[K:]:
        for eij in ei:
            heappush(Q, -eij)

    res = cur + K * K
    for x in reversed(list(range(1, K))):
        v, w = E[x][0], -Q[0]
        if v < w:
            heapreplace(Q, -v)
            cur += w - v

        res = max(res, cur + x * x)

    print(res)

if __name__ == '__main__':
    main()
# Original solution
from heapq import heappush, heappop, heapreplace

def main():
    INF = 10 ** 9 + 7

    N, K, *TD = list(map(int, open(0).read().split()))

    E = [[] for _ in range(N)]
    for t, d in zip(*[iter(TD)] * 2):
        E[t - 1].append(d)

    for e in E:
        if e:
            e.sort(reverse=True)
        else:
            e.append(-INF)
    E.sort(key=lambda x: -x[0])

    cur = 0
    Q = []
    for i in range(K):
        cur += E[i][0]
        for j in range(1, len(E[i])):
            heappush(Q, -E[i][j])

    for i in range(K, N):
        for eij in E[i]:
            heappush(Q, -eij)

    res = cur + K * K
    for x in reversed(list(range(1, K))):
        v, w = E[x][0], -Q[0]
        if v < w:
            heapreplace(Q, -v)
            cur += w - v

        tmp = cur + x * x
        if res < tmp:
            res = tmp

    print(res)

if __name__ == '__main__':
    main()


# Optimized solution
from heapq import heappush, heapreplace

def main():
    INF = 10 ** 9 + 5

    N, K, *TD = list(map(int, open(0).read().split()))

    E = [[] for _ in range(N)]
    for t, d in zip(*[iter(TD)] * 2):
        E[t - 1].append(d)

    for e in E:
        if e:
            e.sort(reverse=True)
        else:
            e.append(-INF)
    E.sort(key=lambda x: -x[0])

    cur = 0
    Q = []
    for ei in E[:K]:
        cur += ei[0]
        for eij in ei[1:]:
            heappush(Q, -eij)

    for ei in E[K:]:
        for eij in ei:
            heappush(Q, -eij)

    res = cur + K * K
    for x in reversed(list(range(1, K))):
        v, w = E[x][0], -Q[0]
        if v < w:
            heapreplace(Q, -v)
            cur += w - v

        tmp = cur + x * x
        if res < tmp:
            res = tmp

    print(res)

if __name__ == '__main__':
    main()
# Original solution
import heapq as hq
from collections import deque
from copy import deepcopy
N, K = list(map(int, input().split()))
Sushi = [None for _ in range(N)]
TotalType = set()
for _ in range(N):
    t, d = list(map(int, input().split()))
    Sushi[_] = [d, t]
Sushi.sort(reverse = True)

ChosenType = set()
Double = []
hq.heapify(Double)
BasePoint = 0
for goodsushi in Sushi[:K]:
    BasePoint += goodsushi[0]
    if goodsushi[1] in ChosenType:
        hq.heappush(Double, goodsushi)
    else: ChosenType |= {goodsushi[1]}

NotChosen = deque(deepcopy(Sushi[K:]))
MaxHappiness = BasePoint + len(ChosenType)**2
while Double and NotChosen:
    TrushPoint, TrushType = hq.heappop(Double)
    BasePoint -= TrushPoint
    while NotChosen:
        addPoint, addType = NotChosen.popleft()
        if addType not in ChosenType:
            BasePoint += addPoint
            ChosenType |= {addType}
            break
    MaxHappiness = max(MaxHappiness, BasePoint + len(ChosenType)**2)
print(MaxHappiness)

# Optimized solution
import sys

def solve():
    input = sys.stdin.readline
    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(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

if __name__ == "__main__":
    solve()
# Original solution
def get_point(l):
  deli = 0
  kind = set()
  for x in l:
    kind = kind | set([x[0]])
    deli += x[1]
  
  point = deli + len(kind) * len(kind)
  return point, kind


def remove_deplicated_kind(l, kind):
  l = [[x[0], x[1]] for x in l if x[0] not in kind]
  return l


def replace_data(curr, rest):
  alt = [rest[0]] + curr[:-1]
  replaced = curr[-1]
  _, kind1 = get_point(curr)
  _, kind2 = get_point(alt)
  
  i = 0
  while len(kind1) >= len(kind2):
    temp = [replaced] + alt[:-1]
    replaced = alt[-1]
    alt = temp
    _, kind2 = get_point(alt)
    i += 1
    if i >= len(curr):
      break
  
  return alt


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

l = sorted(l, key=lambda x: -x[1])
curr = l[:k]
rest = l[k:]

p, kind1 = get_point(curr)
ans = [p]

while len(rest) > 0:
  curr = replace_data(curr, rest)
  p, kind = get_point(curr)
  rest = rest[1:]
  rest = remove_deplicated_kind(rest, kind)
  ans.append(p)

print((max(ans)))

# Optimized solution
import sys

def point(sushi, n, k):
  sushi = sorted(sushi, key=lambda x:-x[1])
  
  ate_t = set()
  dpoint = 0
  dup = []
  for s in sushi[:k]:
    t = s[0]
    d = s[1]
    if t in ate_t:
      dup.append(d)
    ate_t.add(t)
    dpoint += d
  
  ans = len(ate_t)**2 + dpoint
  
  for s in sushi[k:]:
    t = s[0]
    d = s[1]
    if len(dup) <= 0:
      break
    if t in ate_t:
      continue
    ate_t.add(t)
    rm = dup.pop()
    dpoint = dpoint - rm + d
    res = len(ate_t)**2 + dpoint
    ans = max(ans, res)
  
  return ans

def main():
  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([t,d])
  print((point(sushi, n, k)))


if __name__ == '__main__':
  main()
# Original solution
N, K = list(map(int, input().split()))
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
typ = []
lstA = []
lstB = []
for item in sushi:
    if item[0] in typ:
        item[0] = 0
        lstB.append(item[1])
    else:
        typ.append(item[0])
        item[0] = 1
        lstA.append(item[1])
ans = 0
neta = 0
for i in range(K):
    ans += sushi[i][1]
    if sushi[i][0] == 1:
        neta += 1
ans += neta ** 2
C = sum(lstA[:neta])
D = sum(lstB[:K - neta])
for i in range(neta + 1, min(K, len(lstA)) + 1):
    C += lstA[i - 1]
    D -= lstB[K - i]
    tmp = C + D + i ** 2
    ans = max(ans, tmp)
print(ans)

# Optimized solution
N, K = list(map(int, input().split()))
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
typ = set()
lstA = []
lstB = []
for item in sushi:
    if item[0] in typ:
        item[0] = 0
        lstB.append(item[1])
    else:
        typ.add(item[0])
        item[0] = 1
        lstA.append(item[1])
ans = 0
neta = 0
for i in range(K):
    ans += sushi[i][1]
    if sushi[i][0] == 1:
        neta += 1
ans += neta ** 2
C = sum(lstA[:neta])
D = sum(lstB[:K - neta])
for i in range(neta + 1, min(K, len(lstA)) + 1):
    C += lstA[i - 1]
    D -= lstB[K - i]
    tmp = C + D + i ** 2
    ans = max(ans, tmp)
print(ans)
# Original solution
N,K = list(map(int,input().split()))
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[1],reverse=True)
C = {}
tot1 = 0
for i in range(K):
    t,d = A[i]
    if t not in C:
        C[t] = 0
    C[t] += 1
    tot1 += d
tot2 = len(C)
tot = tot1+tot2**2
cur = K
for i in range(K-1,-1,-1):
    t,d = A[i]
    if C[t]>1:
        tot1 -= d
        C[t] -= 1
        j = cur
        while j<N:
            t1,d1 = A[j]
            if t1 not in C:
                C[t1]=1
                tot1 += d1
                tot2 += 1
                if tot1+tot2**2>tot:
                    tot = tot1+tot2**2
                cur = j+1
                break
            else:
                j += 1
print(tot)

# Optimized solution
N,K = list(map(int,input().split()))
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[1],reverse=True)
C = {}
tot1 = 0
for i in range(K):
    t,d = A[i]
    if t not in C:
        C[t] = 0
    C[t] += 1
    tot1 += d
tot2 = len(C)
tot = tot1+tot2**2
cur = K
for i in range(K-1,-1,-1):
    t,d = A[i]
    if C[t]>1:
        tot1 -= d
        C[t] -= 1
        j = cur
        while j<N:
            t1,d1 = A[j]
            if t1 not in C:
                C[t1]=1
                tot1 += d1
                tot2 += 1
                if tot1+tot2**2>tot:
                    tot = tot1+tot2**2
                cur = j+1
                break
            else:
                j += 1
                cur = j
print(tot)