Problem:
 Score : 400 points    Problem Statement 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 1 5 3
1 9
1 7
2 6
2 5
3 1      Sample Output 1 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.       Sample Input 2 7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5      Sample Output 2 25  It is optimal to eat Sushi 1,2,3 and 4 .       Sample Input 3 6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000      Sample Output 3 4900000016  Note that the output may not fit into a 32 -bit integer type.

Solution (Python):
class Sushi(object):
    def __init__(self, sushi_type, delicious):
        self.t = sushi_type
        self.d = delicious


def main() -> None:
    n, k = map(int, input().split())
    menu = [[int(x) for x in input().split()] for _ in range(n)]
    selected = []
    unselected = []
    cnt = 0
    p_satisfied = 0
    selected_type = set()

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

    for i in range(n):
        sushi = Sushi(menu[i][0], menu[i][1])
        if sushi.t not in selected_type and cnt < k:
            selected_type.add(sushi.t)
            cnt += 1
            selected += [menu[i]]
        else:
            unselected += [menu[i]]

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

    while cnt < k and len(unselected) > 0:
        p_satisfied += unselected[-1][1]
        unselected.pop()
        cnt += 1

    while True:
        t_cnt = len(selected)
        if len(selected) == 0 or len(unselected) == 0:
            break
        if t_cnt ** 2 + selected[-1][1] > (t_cnt - 1) ** 2 + unselected[-1][1]:
            break
        p_satisfied += unselected[-1][1]
        unselected.pop()
        selected.pop()

    for v in selected:
        p_satisfied += v[1]

    print(p_satisfied + len(selected) ** 2)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

N,K=map(int, sys.stdin.readline().split()) 
T=[ map(int, sys.stdin.readline().split()) for i in range(N) ]
T=sorted(T, key=lambda x:(x[0],-x[1]))

KI=[]	
A=[]	

x=None
for t,d in T:
	if t != x:
		KI.append(d)
		x=t
	else:
		A.append(d)

KI.sort(reverse=True)
A.sort(reverse=True)

KI_S=[0]		
A_S=[0]		

for x in KI: KI_S.append( KI_S[-1]+x )
for x in A:  A_S.append( A_S[-1]+x )


la=len(A_S)
lk=len(KI_S)

ans=0
for k in range(1,K+1):
	if K-k<la and k<lk:
		ans=max (ans , KI_S[k]+k**2+A_S[K-k] )

print ans

Solution (Python):
a = list(map(lambda x: int(x), input().split()))
N = a[0]
K = a[1]
sushis = []
for i in range(0, N):
  sushis.append(list(map(lambda x: int(x), input().split())))

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

netas = set()
duplicates = []

choices = sushis[:K]

for choice in choices:
  if choice[0] in netas:
    duplicates.append(choice[1])
  else:
    netas.add(choice[0])

p = sum(map(lambda x: x[1], choices)) + len(netas)**2
answer = p

for sushi in sushis[K:]:
  if sushi[0] not in netas and duplicates:
    netas.add(sushi[0])
    duplicate = duplicates.pop()
    p += (sushi[1] - duplicate) + 2*len(netas) - 1
    answer = max(answer, p)

print(answer)

Solution (Python):
from collections import Counter as ct
n, k = map(int, input().split())
td = [list(map(int, input().split())) for i in range(n)]

kind = len(ct(list(map(lambda x: x[0], td))))
std = sorted(td, key=lambda x: x[1], reverse=True)
dup = []
eat_k = set()
ans = 0
for i in range(k):
    ans += std[i][1]
    if std[i][0] in eat_k:
        dup.append(std[i])
    eat_k.add(std[i][0])
ans += len(eat_k)** 2
tmpa = ans
for i in range(k, n):
    if len(dup) == 0:
        break
    if std[i][0] not in eat_k:
        t = dup.pop()
        tmpa -= t[1]
        tmpa += std[i][1]
        tmpa -= len(eat_k)** 2
        eat_k.add(std[i][0])
        tmpa += len(eat_k)** 2
        ans = max(tmpa, ans)
print(ans)

Solution (Python):
N, K = map(int, input().split())
menu_ = []

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

menu = sorted(menu_, key = lambda x:x[1], reverse=True)
neta = set()
duplicates = []

for m in menu[:K]:
    if m[0] in neta:
        duplicates.append(m[1])
    else:
        neta.add(m[0])

p = sum([d for (t, d) in menu[:K]]) + len(neta)**2
ans = p

for m in menu[K:]:
    if m[0] not in neta and duplicates:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        
        ans = max(ans, p)

print(ans)

Solution (Python):
from operator import itemgetter
from functools import reduce
N, K = map(int, input().split())
t, d = zip(*(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)

Solution (Python):
from heapq import heappop,heappush
n,k = (int(i) for i in input().split())
x,y,z,q = [],set(),[0]*n,[]
for _ in range(n):
	t,d = (int(i) for i in input().split())
	x.append((d,t-1))
x,p = sorted(x)[::-1],0
for i in range(k):
	p+=x[i][0]
	z[x[i][1]]+=1
	y.add(x[i][1])
	heappush(q,x[i])
ans,m,l,F = p+len(y)**2,k,len(y),1
while F:
	F = 0
	while q:
		d,t = heappop(q)
		if z[t]!=1:
			f,F,z[t] = 1,1,z[t]-1
			for j in range(m,n):
				if z[x[j][1]]==0:
					z[x[j][1]],m,f,l = 1,j,0,l+1
					p = p-d+x[j][0]
					break
			if f: F = 0
			else: ans = max(ans,p+l**2)
			break
print(ans)

Solution (Python):
import heapq


def func(n, k, td):
    neta = [0 for _ in range(n)]
    td.sort()
    td.reverse()
    _heapq = []
    _sum = 0
    types = 0
    for i in range(k):
        _sum += td[i][0]
        if neta[td[i][1]] == 0:
            types += 1
        if neta[td[i][1]] > 0:  
            heapq.heappush(_heapq, td[i])
        neta[td[i][1]] += 1
    _max = _sum + types**2
    
    for i in range(k, n):
        
        
        if len(_heapq) > 0 and neta[td[i][1]] == 0:  
            tmp = heapq.heappop(_heapq)
            _sum -= tmp[0]
            _sum += td[i][0]
            neta[tmp[1]] -= 1
            types += 1
            neta[td[i][1]] += 1
        
        
        _max = max(_max, _sum + types**2)
    return str(_max)


n, k = [int(i) for i in input().split()]
td = [[0, 0] for _ in range(n)]
for i in range(n):
    td[i][1], td[i][0] = [int(i) for i in input().split()]
    td[i][1] -= 1

print(func(n, k, td))
"""
print(func(5,3,[[9, 0], [7, 0], [6, 1], [5, 1], [1, 2]]))
print(func(7,4,[[1, 0], [1, 1], [1, 2], [6, 3], [5, 3], [5, 3], [5, 3]]))
print(func(6,5,[[1000000000, 4], [990000000, 1], [980000000, 2], [970000000, 5], [960000000, 5], [950000000, 3]]))
"""

Solution (Python):
N,K =map(int,input().split())
sushi = [[int(i)for i in input().split()]for _ in range(N)]
sushi =sorted(sushi,key=lambda x:x[1],reverse=True)
neta =set()
ans = 0
daburi =[]
for i in range(K):
    if sushi[i][0] in neta:
        daburi.insert(0,i)
    neta.add(sushi[i][0])
    ans += sushi[i][1]
n = len(neta)
ans += n*n
sta = K
anslist=[ans]
s=False
while True:
    n =len(neta)
    if daburi == [] or s:
        break
    outsushi = daburi.pop(0)
    for i in range(sta,N):
        if not sushi[i][0] in neta:
            ans -= sushi[outsushi][1]
            ans += sushi[i][1]+2*n+1
            anslist.append(ans)
            neta.add(sushi[i][0])
            sta = i +1
            break
        elif i == N-1:
            s =True

print(max(anslist))

Solution (Python):
N, K = map(int, input().split())
dt = []
for i in range(N):
	t, d = map(int, input().split())
	dt.append((d, t))
dt.sort()
dt.reverse()
dic = {}
can_delete = []
dp = 0
x = 0
for i in range(K):
	d, t = dt[i]
	dp += d
	if t in dic:
		can_delete.append(d)
	else:
		dic[t] = d
		x += 1
can_delete.sort()
can_delete.reverse()
ans = dp + x * x
v = ans
for i in range(K, N):
	if len(can_delete) == 0:
		break
	d, t = dt[i]
	if t in dic:
		continue
	dic[t] = d
	x += 1
	v = v - can_delete.pop() + d + 2 * x - 1
	if v > ans:
		ans = v
print(ans)

Solution (Python):
import heapq
N, K = map(int, input().split())
dt = []
for i in range(N):
	t, d = map(int, input().split())
	dt.append((d, t))
dt.sort()
dt.reverse()
dic = {}
can_delete = []
dp = 0
x = 0
for i in range(K):
	d, t = dt[i]
	dp += d
	if t in dic:
		heapq.heappush(can_delete, d)
	else:
		dic[t] = d
		x += 1
ans = dp + x * x
v = ans
for i in range(K, N):
	if len(can_delete) == 0:
		break
	d, t = dt[i]
	if t in dic:
		continue
	dic[t] = d
	x += 1
	v = v - heapq.heappop(can_delete) + d + 2 * x - 1
	if v > ans:
		ans = v
print(ans)

Solution (Python):
n, k = map(int, input().split())
h = []
for i in range(n):
    t, d = map(int, input().split())
    h.append((t,d))
h.sort(key=lambda x: -x[1])

taste = 0
typen = 0
typecnt = {}
bad = []


for i in range(k):
    typecnt[h[i][0]] = typecnt.get(h[i][0], 0) + 1
    if(typecnt[h[i][0]] == 1):
        typen += 1
    else:
        bad.append(h[i][1])
    taste += h[i][1]





ans = taste + typen**2

for i in range(k, n):
    if(len(bad) == 0):
        break
    cnt = typecnt.get(h[i][0], 0)
    if(cnt != 0):
        continue
    else:
        typecnt[h[i][0]] = cnt + 1
    typen += 1
    taste -= bad.pop()
    taste += h[i][1]
    ans = max(ans, taste + typen**2)

print(ans)

Solution (Python):
from collections import defaultdict

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

items = []
for _ in range(n):
    ti, di = map(int, input().split())
    items.append((di, ti))

items.sort(reverse=True)

topics = defaultdict(int)
for _, ti in items[:k]:
    topics[ti] += 1

best_res = sum(v for v, _ in items[:k]) + len(topics) ** 2
curr_res = sum(v for v, _ in items[:k])

i = k - 1
j = k
while i >= 0 and j < n:
    di, ti = items[i]
    if topics[ti] < 2:
        i -= 1
        continue
    dj, tj = items[j]
    if tj in topics:
        j += 1
        continue
    if topics[ti] > 1:
        topics[ti] -= 1
    else:
        del topics[ti]
    topics[tj] += 1
    curr_res -= di
    curr_res += dj
    best_res = max(curr_res + len(topics) ** 2, best_res)
    i -= 1
        
    

print(best_res)

Solution (Python):

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)

point = 0
stack = []
kind = set()

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

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

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

print(ans)

Solution (Python):
from operator import itemgetter
from heapq import heappush, heappop

N, K = map(int, input().split())
a = []
for i in range(N):
    ta,tb = map(int, input().split())
    a.append([i,ta,tb])
a = sorted(a, key=itemgetter(2), reverse=True)

neta_count = 0
umai = []
umai_append = umai.append
used_i = set()
add_i = used_i.add
used_neta = set()
add_neta = used_neta.add

for i, neta, uma in a:
    if neta not in used_neta:
        umai.append(uma)
        neta_count += 1
        add_i(i)
        add_neta(neta)
    if neta_count == K:
        break

m = neta_count
umai.sort()
for i, neta, uma in filter(lambda x: x[0] not in used_i, a):
    
    if m < K:
        heappush(umai, uma)
        m += 1
    elif uma > umai[0]:
        if neta in used_neta and uma - umai[0] > neta_count**2 - (neta_count-1)**2:
            
            heappop(umai)
            heappush(umai, uma)
            neta_count -= 1

print(sum(umai) + neta_count**2)

Solution (Python):
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td = [(x[0]-1,x[1]) for x in td]
td.sort(key=lambda x:-x[1])

t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[:K]
for i in range(K):
    t[tdK[i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if d_top[td[i][0]] == 0:
        d_top[td[i][0]] = td[i][1]
    else:
        d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
s = sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))

if len(d_rest) == 0:
    print(l**2 + s)
else:
    s += d_rest_cum[-1]
    ans = l**2 + s
    for k in range(min(len(d_rest),len(d_candi))):
        ans = max((l+k+1)**2 + s + d_candi_cum[k] - d_rest_cum[k],ans)

    print(ans)

Solution (Python):
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td = [(x[0]-1,x[1]) for x in td]
td.sort(key=lambda x:-x[1])

t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[:K]
for i in range(K):
    t[tdK[i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if d_top[td[i][0]] == 0:
        d_top[td[i][0]] = td[i][1]
    else:
        d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
s = sum(d_top)
ans = l**2 + s
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))

if len(d_rest) == 0:
    print(ans)
else:
    ans += d_rest_cum[-1]
    s += d_rest_cum[-1]
    for k in range(min(len(d_rest),len(d_candi))):
        ans = max((l+k+1)**2 + s + d_candi_cum[k] - d_rest_cum[k],ans)

    print(ans)

Solution (Python):


"""
参考：https://img.atcoder.jp/abc116/editorial.pdf
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
tdN = [[0]*2 for i in range(N)]
for i in range(N):
    t, d = MAP()
    tdN[i][0] = t
    tdN[i][1] = d

tdN.sort(key=itemgetter(1),reverse=True)
base = 0
bonus = 0
c = Counter()
changes = []
ans = 0
for i in range(K):
    t, d = tdN[i]
    base += d
    if c[t] == 0:
        bonus += 1
    c[t] += 1
    
    if c[t] >= 2:
        heappush(changes, (d, i))
bonus *= bonus
ans = base + bonus

for i in range(K, N):
    t, d = tdN[i]
    
    if c[t] != 0:
        continue
    else:
        
        if len(changes):
            _, idx = heappop(changes)
            t2, d2 = tdN[idx]
            base -= d2 - d
            bonus = (sqrt(bonus)+1) ** 2
            ans = max(base + bonus, ans)
            
            c[t2] -= 1
            c[t] += 1
print(int(ans))

Solution (Python):


def main():
    [N, K] = list(map(int, input().split()))
    s_list = []
    for i in range(N):
        s_list.append(list(map(int, input().split())))

    s_list.sort(key = lambda v: v[1], reverse = True)
    n_set = set()
    A, B = [0], [0]
    tot_a, tot_b = 0, 0
    for td in s_list:
        if not td[0] in n_set:
            n_set.add(td[0])
            tot_a += td[1]
            A.append(tot_a)
        else:
            tot_b += td[1]
            B.append(tot_b)

    min_n = max(1, K - (len(B) - 1))
    max_n = min(K + 1, len(A))
    max_x = 0
    for i in range(min_n, max_n):
        max_x = max(max_x, A[i] + i ** 2 + B[K - i])

    print(max_x)


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop,heappush
N,K=map(int,input().split())
table=[]
for i in range(N):
    t,d=map(int,input().split())
    t=t-1
    table.append((d,t))
table=sorted(table,reverse=True)
L=[0]*N
H=set()
W=[]
ans=-1
num=0
for i in range(K):
    d,t=table[i]
    L[t]+=1
    H.add(t)
    num+=d
    if L[t]>=2:
        heappush(W,(d,t))
ans=len(H)**2+num
for i in range(K,N):
    d,t=table[i]
    L[t]+=1
    if L[t]>=2:
        continue
    if len(W)==0:
        continue
    d1,t1=heappop(W)
    H.add(t)
    num=num-d1+d
    ans=max(ans,len(H)**2+num)
print(ans)

Solution (Python):
from heapq import heappop,heappush
N,K=map(int,input().split())
table=[]
for i in range(N):
    t,d=map(int,input().split())
    t=t-1
    table.append((d,t))
table=sorted(table,reverse=True)
L=[0]*N
H=set()
W=[]
ans=-1
num=0
for i in range(K):
    d,t=table[i]
    L[t]+=1
    H.add(t)
    num+=d
    if L[t]>=2:
        heappush(W,(d,t))
ans=len(H)**2+num
for i in range(K,N):
    d,t=table[i]
    L[t]+=1
    if L[t]>=2:
        continue
    if len(W)==0:
        continue
    d1,t1=heappop(W)
    H.add(t)
    num=num-d1+d
    ans=max(ans,len(H)**2+num)
print(ans)

Solution (Python):
N,K=map(int,input().split())

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=set()
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.add(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=(len(number))**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.add(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)

Solution (Python):
def run(N, K, t, d):
    '''
    おいしさ(d)の昇順でソートする O(NlogN)
    おいしさが大きいもののK個の合計を取得 O(K)
    K個のうちおいしさが少ないものから順にネタの種類が
    増えるように変更していく O(K)
    ネタの種類のうち最大の物の値とインデックスを取得しておく O(K)
    ネタの種類を変えた合計のうち最大のものが答え
    '''
    t_dic = dict(zip(range(N), t))
    d_dic = dict(zip(range(N), d))
    d_dic_sorted = sorted(d_dic.items(), key=lambda x: x[1], reverse=True)
    d_dic_sorted_i = [dd[0] for dd in d_dic_sorted]
    d_dic_sorted_d = [dd[1] for dd in d_dic_sorted]
    d_sum = sum(d_dic_sorted_d[:K])
    t_used = {}
    t_cnt = 0
    for i in t:
        t_used[i] = 0
    for i in d_dic_sorted_i[:K]:
        t_used[t_dic[i]] += 1
        if t_used[t_dic[i]] == 1:
            t_cnt += 1
    t_sum = t_cnt ** 2
    max_sum = d_sum + t_sum
    del_list = d_dic_sorted_i[:K]
    for i in d_dic_sorted_i[K:]:
        di = d_dic[i]
        ti = t_dic[i]
        
        if t_used[ti] == 0:
            t_used[ti] += 1
            t_cnt += 1
            t_sum += 2*t_cnt - 1
            d_sum += di
            
            flg = True
            while len(del_list) > 0 and flg:
                del_i = del_list.pop()
                del_di = d_dic[del_i]
                del_ti = t_dic[del_i]
                if t_used[del_ti] > 1:
                    t_used[del_ti] -= 1
                    d_sum -= del_di
                    max_sum = max(max_sum, d_sum + t_sum)
                    flg = False
    return max_sum


def main():
    N, K = map(int, input().split())
    t = []
    d = []
    for _ in range(N):
        ti, di = map(int, input().split())
        t.append(ti)
        d.append(di)
    print(run(N, K, t, d))


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())

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


vmax = 0
s = set()
q = []
for i in range(K):
    vmax += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
vmax += len(s)**2   




i += 1   
v = vmax
while i < N and q:
    if a[i][0] not in s:
        v -= q.pop() + len(s)**2
        v += a[i][1] + (len(s)+1)**2
        vmax = max(vmax, v)
        s.add(a[i][0])
    i += 1


print(vmax)

Solution (Python):
n, k = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:-x[1])
 
ans = 0
s = set()
q = []
 
for i in range(k):
    ans += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
 
ans += len(s)**2
k1 = k
ans1 = ans
 

while k1 < n and q:
    if a[k1][0] not in s:
        ans1 = ans1+a[k1][1]-q.pop()-len(s)**2+(len(s)+1)**2
        ans = max(ans, ans1)
        s.add(a[k1][0])
    k1 += 1
 
print(ans)

Solution (Python):
from statistics import mean, median,variance,stdev
import sys
import math
import fractions

def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())


n,k= (int(i) for i in input().split())      







a = []
o = []
p = []
for i in range(n):
    c,d = (int(i) for i in input().split())
    o.append([c,d])
    a.append([d,c])
    p.append(d)
a.sort(reverse=True)

cstackd = []
nestackd = []
nestackt =[]
nneed = []
ctset = set()
sum = 0
for i in range(k):
    if a[i][1] in ctset:
        nneed.append(a[i][0])
    else : ctset.add(a[i][1])
    sum+=a[i][0]

ans = pow(len(ctset),2)+sum
for i in range(k,len(a)):
    if len(nneed) == 0: break
    if a[i][1] not in ctset: 
        sum -= nneed.pop()
        sum+= a[i][0]
        ctset.add(a[i][1])
        ans = max (pow(len(ctset),2) + sum,ans)


print(ans)

Solution (Python):
n, k =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)

Solution (Python):
n, k = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:-x[1])

ans = 0
s = set()
q = []

for i in range(k):
    ans += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])

ans += len(s)**2
k1 = k
ans1 = ans


while k1 < n and q:
    if a[k1][0] not in s:
        ans1 = ans1+a[k1][1]-q.pop()-len(s)**2+(len(s)+1)**2
        ans = max(ans, ans1)
        s.add(a[k1][0])
    k1 += 1

print(ans)

Solution (Python):
N,K=map(int,input().split())
td=[[int(a) for a in input().split()]for i in range(N)]

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

ans=0
eat=set([])
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.add(t)
  else:
    noteat.append(d)
temp_result=ans+len(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.add(t)
    max_result=max(max_result,temp_result)
print(max_result)

Solution (Python):

"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

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

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k+i-1])

print(max(ans))

Solution (Python):
from collections import deque as dq
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)
ls = set()
dl = dq()
ans = 0
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans -= dl[-1]
    ans -= len(ls)*len(ls)
    ls.add(td[i][0])
    ans += len(ls)*len(ls)
    ans += td[i][1]
    del dl[-1]
    res = max(res,ans)
print(res)

Solution (Python):
N,K = map(int,input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x:x[1],reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans += len(ls)*2+1
    ans += td[i][1]
    ans -= dl[-1]
    del dl[-1]
    res = max(res,ans)
    ls.add(td[i][0])
print(res)

Solution (Python):
import heapq as hq
from collections import deque
from copy import deepcopy
N, K = map(int, input().split())
Sushi = [None for _ in range(N)]
TotalType = set()
for _ in range(N):
    t, d = 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)

Solution (Python):
from collections import *
n, k = map(int, input().split())
d, t = 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)

Solution (Python):
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()

Solution (Python):

"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

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

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k+i-1])

print(max(ans))

Solution (Python):
N,K = map(int,input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x:x[1],reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans += len(ls)*2+1
    ans += td[i][1]
    ans -= dl[-1]
    del dl[-1]
    res = max(res,ans)
    ls.add(td[i][0])
print(res)

Solution (Python):



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


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



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



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

    
    if len(sel_sushis) == 0:
        break
    t1, d1 = sel_sushis.pop()
    sum_oishisa -= d1

    
    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)

Solution (Python):
from math import pow
from collections import deque, Counter
import sys
stdin = sys.stdin
def li(): return map(int, stdin.readline().split())

def cal_score(N, K, records):
    sorted_recs = sorted(records, key=lambda x: -x[1])
    target_queue = deque(sorted_recs[0:K]) 
    compare_queue = deque(sorted_recs[K:])
    distinct_set = set()
    dup_queue = deque()
    score = 0
    for neta_point in target_queue:
        score += neta_point[1]
        if neta_point[0] not in distinct_set:
            distinct_set.add(neta_point[0])
        else:
            dup_queue.append(neta_point)

    cardinality = len(distinct_set)
    score += pow(cardinality, 2)
    score = int(score)
    maybe_score = score
    
    while compare_queue:
        comp = compare_queue.popleft()
        if comp[0] in distinct_set:
            continue
        elif len(dup_queue) < 1:
            break
        else:
            old = dup_queue.pop()
            inc = 2 * len(distinct_set) + 1
            dec = old[1] - comp[1]
            delta = inc - dec
            maybe_score = maybe_score + delta
            score = max(score, maybe_score)

            distinct_set.add(comp[0])
    
    return score


N, K = li()
records = [tuple(li()) for i in range(N)]
score = cal_score(N, K, records)
print(score)