import heapq



INF = float('inf')

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

sushi = {}



for _ in range(n):

    t, d = list(map(int, input().split()))

    if t not in sushi:

        sushi[t] = []

    sushi[t].append(d)



for s in list(sushi.values()):

    s.sort(reverse=True)



eat_counts = {s: 0 for s in list(sushi.keys())}



# まだ食べてないやつ

news = []

# リピート

repeats = []

# 食べた履歴

eats = []



# 各寿司の一番おいしいやつを heap へ

for name, deli_li in list(sushi.items()):

    # (-おいしさ, name)

    heapq.heappush(news, (-deli_li[0], name))



sum_deli = 0

variety = 0



for _ in range(k):

    # おいしいやつから食べる

    if news and (not repeats or news[0] <= repeats[0]):

        deli, name = heapq.heappop(news)

        variety += 1

    else:

        deli, name = heapq.heappop(repeats)



    sum_deli += -deli

    eat_counts[name] += 1

    heapq.heappush(eats, (-deli, name))

    if eat_counts[name] < len(sushi[name]):

        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))



# 美味しいやつから順に食べた

# 種類増やしたらもっと得点上がるか確かめる

ans = sum_deli + variety ** 2

while True:

    if not news or not eats:

        break



    # 食べたやつポイント小さいやつから置き換えたい

    ate_min_deli, ate_min_name = heapq.heappop(eats)

    eat_counts[ate_min_name] -= 1

    if eat_counts[ate_min_name] <= 0:

        # これは種類減っちゃうからだめ

        continue



    sum_deli -= ate_min_deli



    deli, name = heapq.heappop(news)

    variety += 1

    sum_deli += -deli

    eat_counts[name] += 1



    ans = max(ans, sum_deli + variety ** 2)



print(ans)

import os

import sys

from collections import deque

from operator import itemgetter



if os.getenv("LOCAL"):

    sys.stdin = open("_in.txt", "r")



sys.setrecursionlimit(10 ** 9)

INF = float("inf")

IINF = 10 ** 18

MOD = 10 ** 9 + 7

# MOD = 998244353



N, K = list(map(int, sys.stdin.buffer.readline().split()))

TD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]



t_seen = [False] * (N + 1)

sushi_seen = [False] * N

TD.sort(key=itemgetter(1), reverse=True)



delicious = 0

que = deque()

for i, (t, d) in enumerate(TD):

    if len(que) >= K:

        break

    if not t_seen[t]:

        que.append(i)

        delicious += d

        t_seen[t] = True

        sushi_seen[i] = True

for i, (t, d) in enumerate(TD):

    if len(que) >= K:

        break

    if not sushi_seen[i]:

        que.appendleft(i)

        delicious += d

        sushi_seen[i] = True



idx = i

type_cnt = sum(t_seen)

ans = delicious + type_cnt ** 2

while idx < que[-1]:

    while idx < N and sushi_seen[idx]:

        idx += 1

    if idx >= N:

        break

    que.appendleft(idx)

    delicious -= TD[que.pop()][1]

    delicious += TD[idx][1]

    type_cnt -= 1

    score = delicious + type_cnt ** 2

    ans = max(ans, score)

    sushi_seen[idx] = True

print(ans)

import heapq

INF = float("inf")
n, k = list(map(int, input().split()))
sushi = {}
for _ in range(n):
    t, d = list(map(int, input().split()))
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)
for s in list(sushi.values()):
    s.sort(reverse=True)
eat_counts = {s: 0 for s in list(sushi.keys())}
# まだ食べてないやつ
news = []
# リピート
repeats = []
# 食べた履歴
eats = []
# 各寿司の一番おいしいやつを heap へ
for name, deli_li in list(sushi.items()):
    # (-おいしさ, name)
    heapq.heappush(news, (-deli_li[0], name))
sum_deli = 0
variety = 0
for _ in range(k):
    # おいしいやつから食べる
    if news and (not repeats or news[0] <= repeats[0]):
        deli, name = heapq.heappop(news)
        variety += 1
    else:
        deli, name = heapq.heappop(repeats)
    sum_deli += -deli
    eat_counts[name] += 1
    heapq.heappush(eats, (-deli, name))
    if eat_counts[name] < len(sushi[name]):
        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))
# 美味しいやつから順に食べた
# 種類増やしたらもっと得点上がるか確かめる
ans = sum_deli + variety**2
while True:
    if not news or not eats:
        break
    # 食べたやつポイント小さいやつから置き換えたい
    ate_min_deli, ate_min_name = heapq.heappop(eats)
    eat_counts[ate_min_name] -= 1
    if eat_counts[ate_min_name] <= 0:
        # これは種類減っちゃうからだめ
        continue
    sum_deli -= ate_min_deli
    deli, name = heapq.heappop(news)
    variety += 1
    sum_deli += -deli
    eat_counts[name] += 1
    ans = max(ans, sum_deli + variety**2)
print(ans)

import os
import sys
from collections import deque
from operator import itemgetter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
sys.setrecursionlimit(10**9)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7
# MOD = 998244353
N, K = list(map(int, sys.stdin.buffer.readline().split()))
TD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
t_seen = [False] * (N + 1)
sushi_seen = [False] * N
TD.sort(key=itemgetter(1), reverse=True)
delicious = 0
que = deque()
for i, (t, d) in enumerate(TD):
    if len(que) >= K:
        break
    if not t_seen[t]:
        que.append(i)
        delicious += d
        t_seen[t] = True
        sushi_seen[i] = True
for i, (t, d) in enumerate(TD):
    if len(que) >= K:
        break
    if not sushi_seen[i]:
        que.appendleft(i)
        delicious += d
        sushi_seen[i] = True
idx = i
type_cnt = sum(t_seen)
ans = delicious + type_cnt**2
while idx < que[-1]:
    while idx < N and sushi_seen[idx]:
        idx += 1
    if idx >= N:
        break
    que.appendleft(idx)
    delicious -= TD[que.pop()][1]
    delicious += TD[idx][1]
    type_cnt -= 1
    score = delicious + type_cnt**2
    ans = max(ans, score)
    sushi_seen[idx] = True
print(ans)

-import heapq +import os +import sys +from collections import deque +from operator import itemgetter +if os.getenv("LOCAL"): +    sys.stdin = open("_in.txt", "r") +sys.setrecursionlimit(10**9) -n, k = list(map(int, input().split())) -sushi = {} -for _ in range(n): -    t, d = list(map(int, input().split())) -    if t not in sushi: -        sushi[t] = [] -    sushi[t].append(d) -for s in list(sushi.values()): -    s.sort(reverse=True) -eat_counts = {s: 0 for s in list(sushi.keys())} -# まだ食べてないやつ -news = [] -# リピート -repeats = [] -# 食べた履歴 -eats = [] -# 各寿司の一番おいしいやつを heap へ -for name, deli_li in list(sushi.items()): -    # (-おいしさ, name) -    heapq.heappush(news, (-deli_li[0], name)) -sum_deli = 0 -variety = 0 -for _ in range(k): -    # おいしいやつから食べる -    if news and (not repeats or news[0] <= repeats[0]): -        deli, name = heapq.heappop(news) -        variety += 1 -    else: -        deli, name = heapq.heappop(repeats) -    sum_deli += -deli -    eat_counts[name] += 1 -    heapq.heappush(eats, (-deli, name)) -    if eat_counts[name] < len(sushi[name]): -        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name)) -# 美味しいやつから順に食べた -# 種類増やしたらもっと得点上がるか確かめる -ans = sum_deli + variety**2 -while True: -    if not news or not eats: +IINF = 10**18 +MOD = 10**9 + 7 +# MOD = 998244353 +N, K = list(map(int, sys.stdin.buffer.readline().split())) +TD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)] +t_seen = [False] * (N + 1) +sushi_seen = [False] * N +TD.sort(key=itemgetter(1), reverse=True) +delicious = 0 +que = deque() +for i, (t, d) in enumerate(TD): +    if len(que) >= K: -    # 食べたやつポイント小さいやつから置き換えたい -    ate_min_deli, ate_min_name = heapq.heappop(eats) -    eat_counts[ate_min_name] -= 1 -    if eat_counts[ate_min_name] <= 0: -        # これは種類減っちゃうからだめ -        continue -    sum_deli -= ate_min_deli -    deli, name = heapq.heappop(news) -    variety += 1 -    sum_deli += -deli -    eat_counts[name] += 1 -    ans = max(ans, sum_deli + variety**2) +    if not t_seen[t]: +        que.append(i) +        delicious += d +        t_seen[t] = True +        sushi_seen[i] = True +for i, (t, d) in enumerate(TD): +    if len(que) >= K: +        break +    if not sushi_seen[i]: +        que.appendleft(i) +        delicious += d +        sushi_seen[i] = True +idx = i +type_cnt = sum(t_seen) +ans = delicious + type_cnt**2 +while idx < que[-1]: +    while idx < N and sushi_seen[idx]: +        idx += 1 +    if idx >= N: +        break +    que.appendleft(idx) +    delicious -= TD[que.pop()][1] +    delicious += TD[idx][1] +    type_cnt -= 1 +    score = delicious + type_cnt**2 +    ans = max(ans, score) +    sushi_seen[idx] = True