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):
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]


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


fix_eated_d=[]

change_eated_d=[]

eated_t = set()
d_point = 0


for t,d in td[:k]:
  
  
  if t in eated_t:
    change_eated_d.append(d)
    
  
  else:
    fix_eated_d.append(d)
    eated_t.add(t)
    
  d_point += d
  
point = len(eated_t)**2 + d_point


for t,d in td[k:]:
  
  if not change_eated_d:
    break
  
  
  if t in eated_t:
    continue
    
  
  eated_t.add(t)
  d_point += d - change_eated_d.pop()
  point = max(point, len(eated_t)**2 + d_point)
  
print(point)

Solution (Python):
N, K = list(map(int, input().split()))
td = sorted([list(map(int, input().split())) for _ in range(N)],key=lambda x:-x[1])
q = []
ans = 0
s = set()
for i in range(K):
    ans += td[i][1]
    if td[i][0] in s:
        q.append(td[i][1])
    s.add(td[i][0])
ans += len(s)**2
k1 = K
ans1 = ans
while k1 < N and q:
    if td[k1][0] not in s:
        ans1 += td[k1][1] - q.pop() - len(s)**2 + (len(s)+1)**2
        ans = max(ans,ans1)
        s.add(td[k1][0])
    k1 += 1
print(ans)

Solution (Python):

import sys
from collections import defaultdict
from itertools import accumulate
import heapq

def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    sushi = defaultdict(list)
    for i in range(N):
        sushi[t[i]].append(d[i])

    A = [] 
    B = [] 
    
    for v in sushi.values():
        v.sort(reverse=True)
        A.append(v[0])
        B.extend(v[1:])
    A.sort(reverse=True)
    B.sort(reverse=True)

    X = [0] + [x for x in accumulate(A)] 
    Y = [0] + [y for y in accumulate(B)] 

    res = 0
    for i in range(1, min(len(X), K + 1)):
        if K - i < len(Y):
            res = max(res, X[i] + Y[K - i] + i ** 2) 
            
            
            
    print(res)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
from itertools import accumulate

input = sys.stdin.readline

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

X, Y = [], []
for v in sushi.values():
    v = sorted(v, reverse=True)
    X.append(v[0])
    if len(v) > 1:
        Y += v[1:]
X = sorted(X, reverse=True)
Y = sorted(Y, reverse=True)

X = [0] + [x for x in accumulate(X)]
Y = [0] + [x for x in accumulate(Y)]

ans = 0
for i in range(1, min(len(X), K + 1)):
    j = K - i
    if j < len(Y):
        ans = max(ans, X[i] + Y[j] + i * i)
print(ans)

Solution (Python):
N,K = 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)

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

typ = set()
ans = 0
cur = 0
rem = []

for t,d in sushi:
	if t in typ:
		if K > 0:
			K -= 1
			cur += d
			rem.append(d)
	else:
		typ.add(t)
		cur += d
		if K > 0:
			K -= 1
		elif len(rem):
			cur -= rem.pop()
		else:
			break

	ans = max(ans, cur + len(typ)**2)

print(ans)

Solution (Python):
import heapq

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

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

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

g1 = [0] * (N + 1)
g0 = []
sumt = 0
for i in range(K):
    t, d = td[i]
    if g1[t] == 0:
        g1[t] = d
        sumt += 1
    elif g1[t] < d:
        heapq.heappush(g0, g1[t])
        g1[t] = d
    else:
        heapq.heappush(g0, d)

sumg1 = sum(g1)
sumg0 = sum(g0)
ans = sumg1 + sumg0 + sumt * sumt
for i in range(K, N):
    t, d = td[i]
    if g1[t] == 0 and len(g0) > 0:
        g1[t] = d
        sumg1 += d
        sumg0 -= heapq.heappop(g0)
        sumt += 1
        newans = sumg1 + sumg0 + sumt * sumt
        ans = max(ans, newans)

print(ans)

Solution (Python):
import heapq

N, K = map(int, input().split())
heap = []
types = [0 for _ in range(N)]

class Sushi():
    def __init__(self, neta, aji):
        self.neta = neta - 1
        self.aji = aji

    def __str__(self):
        return "Sushi{0}: {1}".format(self.neta, self.aji)

    def reverse(self):
        self.aji = -self.aji

    def __lt__(self, other):
        return self.aji < other.aji

for _ in range(N):
    t, d = map(int, input().split())
    heap.append(Sushi(t, -d))
heapq.heapify(heap)

variety = 0
basic = 0
choices = []
for _ in range(K):
    sushi = heapq.heappop(heap)
    sushi.reverse()
    basic += sushi.aji
    neta = sushi.neta
    if types[neta] == 0:
        variety += 1
    types[neta] += 1
    choices.append(sushi)
heapq.heapify(choices)

satisfaction = basic + variety * variety
top_satisfaction = satisfaction
while True:
    drop_sushi = None
    while len(choices) > 0:
        choiced_sushi = heapq.heappop(choices)
        if types[choiced_sushi.neta] > 1:
            drop_sushi = choiced_sushi
            types[choiced_sushi.neta] -= 1
            break
    add_sushi = None
    while len(heap) > 0:
        new_sushi = heapq.heappop(heap)
        new_sushi.reverse()
        if types[new_sushi.neta] == 0:
            types[new_sushi.neta] += 1
            add_sushi = new_sushi
            break
    if drop_sushi is None or add_sushi is None:
        break
    else:
        variety += 1
        basic += add_sushi.aji - drop_sushi.aji
        satisfaction = basic + variety * variety
        if satisfaction > top_satisfaction:
            top_satisfaction = satisfaction
print(top_satisfaction)

Solution (Python):
N,K=map(int, input().split())
td=[list(map(int,input().split())) for i in range(N)]
best=[0]*(N+1)
other=[]
from heapq import heappop,heappush
td.sort(key=lambda x: x[1],reverse=True)
shurui=0
for i in range(K):
    if best[td[i][0]]==0:
        best[td[i][0]]=td[i][1]
        shurui+=1
    elif best[td[i][0]]<td[i][1]:
        heappush(other,best[td[i][0]])
        best[td[i][0]]=td[i][1]
    else:
        heappush(other,td[i][1])

sumbest=sum(best)
sumother=sum(other)
ans=sumbest+sumother+shurui**2

for i in range(K,N):
    if best[td[i][0]]==0 and len(other)>0:
        best[td[i][0]]=td[i][1]
        shurui+=1
        sumbest+=td[i][1]
        sumother-=heappop(other)
        ans=max(ans,sumbest+sumother+shurui**2)

print(ans)

Solution (Python):
N , K = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]
top = [-10**10]*(N+1)
sub = [0]
cnt = 0
for t, d in sushi:
    if top[t] < d:
        sub.append(top[t])
        top[t] = d
    else:
        sub.append(d)
top.sort(reverse = True)
sub.sort(reverse = True)
top_dp = [0] *(N+1)
sub_dp = [0] * (N+2)
top_dp[1] = top[0]
sub_dp[1] = sub[0]
for i in range(1, N):
    top_dp[i+1] = top_dp[i] + top[i]
for i in range(1, len(sub)):
    sub_dp[i+1] = sub_dp[i] + sub[i]
dp = [0] * (K+1)
for i in range(1, K+1):
    dp[i] = top_dp[i] + sub_dp[K-i] + i*i
print(max(dp))

Solution (Python):
N , K = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]
top = [-10**10]*(N+1)
sub = [0]
cnt = 0
for t, d in sushi:
    if top[t] < d:
        sub.append(top[t])
        top[t] = d
    else:
        sub.append(d)
top.sort(reverse = True)
sub.sort(reverse = True)
top_dp = [0] *(N+1)
sub_dp = [0] * (N+2)
top_dp[1] = top[0]
sub_dp[1] = sub[0]
for i in range(1, N):
    top_dp[i+1] = top_dp[i] + top[i]
for i in range(1, len(sub)):
    sub_dp[i+1] = sub_dp[i] + sub[i]
dp = [0] * (K+1)
for i in range(1, K+1):
    dp[i] = top_dp[i] + sub_dp[K-i] + i*i
print(max(dp))

Solution (Python):
nk = input().split()
n = int(nk[0])
k = int(nk[1])

dtlist = []
for i in range(n):
    td = input().split()
    t = int(td[0])
    d = int(td[1])
    dtlist.append((d, t))
dtlist.sort(reverse=True)


t_to_maxidx = {}
for idx, dt in enumerate(dtlist):
    d, t = dt
    if t not in t_to_maxidx:
        t_to_maxidx[t] = idx


selected = []
count = 0
tcount = {}

candidate = [(dtlist[idx][0], idx) for t, idx in t_to_maxidx.items()]
candidate.sort(reverse=True)
for d, idx in candidate:
    if count >= k:
        break
    d, t = dtlist[idx]
    selected.append(dtlist[idx])
    count += 1
    tcount[t] = 1 if t not in tcount else tcount[t] + 1
    dtlist[idx] = None

new_dtlist = []
for dt in dtlist:
    if dt is not None:
        new_dtlist.append(dt)
dtlist = new_dtlist


if k - count > 0:
    for i in range(k - count):
        dt = dtlist.pop(0)
        selected.append(dt)
        d, t = dt
        tcount[t] = 1 if t not in tcount else tcount[t] + 1

selected.sort()

score = 0
for d, t in selected:
    score += d

len_tcount = len(tcount)
score += len_tcount * len_tcount

for i in range(0, 2**32):
    next_score = score
    try:
        d_new, t_new = dtlist.pop(0)
        d_old, t_old = selected.pop(0)
    except IndexError:
        print(score)
        break
    next_score += d_new
    next_score -= d_old

    tcount[t_old] -= 1
    if tcount[t_old] <= 1:
        next_score -= len_tcount * len_tcount
        len_tcount -= 1
        next_score += len_tcount * len_tcount
        del tcount[t_old]

    if t_new not in tcount:
        next_score -= len_tcount * len_tcount
        len_tcount += 1
        next_score += len_tcount * len_tcount
        tcount[t_new] = 1
    else:
        tcount[t_new] += 1

    if next_score <= score:
        print(score)
        break
    score = next_score

Solution (Python):
import heapq
from collections import defaultdict

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

sushi = []
for _ in range(N):
    kind, value = map(int, input().split())
    sushi.append((value,kind))
sushi.sort()


choice = []
heapq.heapify(choice)

current_sum = 0
kinds = set()
count_nitems_bykind = defaultdict(int)


for _ in range(K):
    item = sushi.pop()
    count_nitems_bykind[item[1]] += 1
    kinds.add(item[1])
    current_sum += item[0]
    heapq.heappush(choice, item)



max_value = {len(kinds):current_sum}


def replace():
    '''
    Returns a next sushi that is new in kind and has maximum value
    '''

    while sushi:
        candidate = sushi.pop()
        if candidate[1] not in kinds:
            kinds.add(candidate[1])
            return candidate

    return None

while sushi and choice:
    
    sushi_min = heapq.heappop(choice)

    
    if count_nitems_bykind[sushi_min[1]] > 1:

        
        sushi_new = replace()
        if sushi_new is None:
            break

        count_nitems_bykind[sushi_min[1]] -= 1
        heapq.heappush(choice, sushi_new)


        
        current_sum = current_sum - sushi_min[0] + sushi_new[0]
        max_value[len(kinds)] = current_sum

    if len(kinds) == K: 
        break

ans = -1

for key in max_value:
    ans = max(ans, max_value[key] + key**2)

print(ans)

Solution (Python):
def solve(string):
    n, k, *td = map(int, string.split())
    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    r, v, b = [], set([]), 0
    for _c in choice:
        b += _c[1]
        if _c[0] in v:
            r.append(_c[1])
        else:
            v.add(_c[0])
    b += len(v)**2
    i = k
    ans = [b]
    while len(v) < min(max_variety, k):
        while td[i][0] in v:
            i += 1
        v.add(td[i][0])
        ans.append(ans[-1] - r.pop() + td[i][1] + 2 * len(v) - 1)
    return str(max(ans))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
def solve(string):
    n, k, *td = map(int, string.split())
    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    r = []
    variety = set([])
    base = 0
    for _c in choice:
        base += _c[1]
        if _c[0] in variety:
            r.append(_c[1])
        else:
            variety.add(_c[0])
    base += len(variety)**2
    i = k
    ans = [base]
    while len(variety) < min(max_variety, k):
        while td[i][0] in variety:
            i += 1
        variety.add(td[i][0])
        ans.append(ans[-1] - r.pop() + td[i][1] + 2 * len(variety) - 1)
    return str(max(ans))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
def solve(string):
    n, k, *td = map(int, string.split())
    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    count = [0] * n
    for _c in choice:
        count[_c[0] - 1] += 1
    variety = set([c[0] for c in choice])
    ans = [len(variety)**2 + sum([c[1] for c in choice])]
    i_remove, i_append = k - 1, k
    while len(variety) < min(max_variety, k):
        while td[i_append][0] in variety:
            i_append += 1
        while count[td[i_remove][0] - 1] == 1:
            i_remove -= 1
        variety.add(td[i_append][0])
        count[td[i_remove][0] - 1] -= 1
        ans.append(ans[-1] - td[i_remove][1] + td[i_append][1] + 2 * len(variety) - 1)
        i_remove -= 1
        i_append += 1
    return str(max(ans))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
def solve(string):
    n, k, *td = map(int, string.split())
    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    count = [0] * n
    r = []
    for _c in choice:
        if count[_c[0] - 1] > 0:
            r.append(_c[1])
        count[_c[0] - 1] += 1
    variety = set([c[0] for c in choice])
    ans = [len(variety)**2 + sum([c[1] for c in choice])]
    i_append = k
    while len(variety) < min(max_variety, k):
        while td[i_append][0] in variety:
            i_append += 1
        variety.add(td[i_append][0])
        ans.append(ans[-1] - r.pop() + td[i_append][1] + 2 * len(variety) - 1)
    return str(max(ans))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
from operator import itemgetter
from collections import Counter

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

sushi = sorted(sushi, key=itemgetter(1), reverse=True)










kind = set()
can_converts = []  
max_pt = 0

for i in range(K):
    if sushi[i][0] in kind:
        can_converts.append(sushi[i])
    else:
        kind.add(sushi[i][0])
    max_pt += sushi[i][1]
max_pt += len(kind) ** 2


curr_pt = max_pt

for s in sushi[K:]:
    if not can_converts: break
    if s[0] not in kind:
        target = can_converts.pop(-1)
        curr_pt = curr_pt - target[1] + s[1] - len(kind) ** 2 + (len(kind) + 1) ** 2
        max_pt = max(max_pt,curr_pt)

        kind.add(s[0])

print(max_pt)

Solution (Python):
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)
A=td[:K]
B=[]
s2=set()
for i,j in td[K:]:
    if not(i in s2):
        s2.add(i)
        B.append([i,j])
s1=set()
n=0
C=[]
sum=0
for i,j in A:
    if not(i in s1):
        s1.add(i)
        n+=1
        sum+=j
    else:
        C.append([i,j])
        sum+=j
sum+=n**2
B.reverse()
D=[]
for i,j in B:
    if not(i in s1):
        D.append([i,j])
list=[sum]

while(C):
    if D:
        i,j=D.pop()
        list.append(list[-1]+2*n+1+(j-C[-1][1]))
        n+=1
    C.pop()
print(max(list))

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

max_kiso = sum([d for t,d in TD[:K]])
classes = set([t for t,d in TD[:K]])
n_classes = len(classes)

from itertools import groupby, accumulate
to_remove = []
for k,g in groupby(sorted(TD[:K]), key = lambda x:x[0]):
    
    to_remove.extend(list(g)[:-1]) 
d_to_remove = sorted([d for t,d in to_remove])
d_to_remove_cumsum = list(accumulate(d_to_remove))

assert n_classes + len(to_remove) == K

to_add = []
for k,g in groupby(sorted(TD[K:]), key = lambda x:x[0]):
    if k not in classes:
        to_add.append(list(g)[-1]) 
d_to_add = sorted([d for t,d in to_add], reverse= True)
d_to_add_cumsum = list(accumulate(d_to_add))

answer = max_kiso + n_classes **2
for i in range(0, min(len(to_remove), len(to_add))):
    a = max_kiso + d_to_add_cumsum[i] - d_to_remove_cumsum[i] + (n_classes + i+1)**2
    answer = max(a,answer)

print(answer)

Solution (Python):
N, K = map(int, input().split())
TD = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: -x[1])
q = []
ans = 0
s = set()
for i in range(K):
    ans += TD[i][1]
    if TD[i][0] in s:
        q.append(TD[i][1])
    s.add(TD[i][0])
ans += len(s) ** 2
k1 = K
ans1 = ans
while k1 < N and q:
    if TD[k1][0] not in s:
        ans1 = ans1 + TD[k1][1] - q.pop() - len(s) ** 2 + (len(s) + 1) ** 2
        ans = max(ans, ans1)
        s.add(TD[k1][0])
    k1 += 1
print(ans)

Solution (Python):
N, K = map(int, input().split())
TD = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: -x[1])
q = []
ans = 0
s = set()
for i in range(K):
    ans += TD[i][1]
    if TD[i][0] in s:
        q.append(TD[i][1])
    s.add(TD[i][0])
ans += len(s) ** 2
k1 = K
ans1 = ans
while k1 < N and q:
    if TD[k1][0] not in s:
        ans1 = ans1 + TD[k1][1] - q.pop() - len(s) ** 2 + (len(s) + 1) ** 2
        ans = max(ans, ans1)
        s.add(TD[k1][0])
    k1 += 1
print(ans)

Solution (Python):
n,k=map(int, input().split())
a=sorted([list(map(int, input().split())) for i in range(n)], key=lambda x:-x[1])
q=[]
ans=0
s=set()
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 heapq import*
I=lambda:list(map(int,input().split()))[::-1]
k,n=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for b,a in sorted(eval('I(),'*n))[::-1]:
 if i<k:
  if l[a]:heappush(q,b)
  else:T+=v*2+1;v+=1
  T+=b
 elif l[a]^1and q:T+=b+v*2+1-heappop(q);v+=1
 A=max(A,T);i+=1;l[a]=1
print(A)

Solution (Python):
import sys
import heapq

n,k=map(int,input().split())
sushi=[[int(i) for i in l.split()] for l in sys.stdin]

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


summation=0
various=0
stack=[0]*(n+1)
heap_min=[]
for i in range(k):
  if stack[sushi[i][0]]==0:
    stack[sushi[i][0]]=1
    various+=1
  else:
    heap_min.append(sushi[i][1])
  summation+=sushi[i][1]


heap_max=[]
for i in range(k,n):
  if stack[sushi[i][0]]==0:
    stack[sushi[i][0]]=1
    heap_max.append((-sushi[i][1],sushi[i][1]))

heapq.heapify(heap_min)
heapq.heapify(heap_max)

ans=summation+various*various
for i in range(1,k-various+1):
  if len(heap_min)==0 or len(heap_max)==0:
    break
  summation-=heapq.heappop(heap_min)
  summation+=heapq.heappop(heap_max)[1]
  ans=max(ans,summation+(various+i)*(various+i))

print(ans)

Solution (Python):
N,K=map(int,input().split())
Sushi=[[int(i) for i in input().split()] for j in range(N)]
Sushi=sorted(Sushi,key=lambda x:x[1],reverse=True)
inp={}
for t,d in Sushi:
    if not t in inp:
        inp[t]=d
tasty=0
neta=set()
dup=[]
for i in range(K):
    t,d=Sushi[i]
    tasty+=d
    if t in neta:
        dup.append((t,d))
    neta.add(t)
    if t in inp:
        del inp[t]
variety=len(neta)
max_tasty=tasty+variety**2
for s,t in sorted(inp.items(),key=lambda x:x[1],reverse=True):
    if len(dup):
        s1,t1=dup.pop()
        variety+=1
        tasty=tasty-t1+t
        max_tasty=max(max_tasty,tasty+variety**2)
print(max_tasty)

Solution (Python):
import heapq

INF = float('inf')
n, k = map(int, input().split())
sushi = {}

for _ in range(n):
    t, d = map(int, input().split())
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)

for s in sushi.values():
    s.sort(reverse=True)

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


news = []

repeats = []

eats = []


for name, deli_li in sushi.items():
    
    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)

Solution (Python):
num_lines, max_num = map(int, input().split())

inp_sorted = [[int(st) for st in input().split()] for _ in range(num_lines)]

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

inp_map = {}
for t, d in inp_sorted:
    if not t in inp_map:
        inp_map[t] = d

variety = set()
score = 0

dup = []
for i in range(max_num):
    t, d = inp_sorted[i]
    if t in variety:
        dup.append((t,d))
    variety.add(t)
    if t in inp_map:
        del inp_map[t]
    score += d

var_value = len(variety)
max_score = score + var_value*var_value

for t, d in sorted(inp_map.items(), key=lambda x: x[1], reverse=True):
    if (len(dup)):
        t2, d2 = dup.pop()
        var_value += 1
        score = score - d2 + d
        max_score = max(max_score, score + var_value*var_value)

print(max_score)

Solution (Python):
import heapq

N,K=map(int,input().split())
L=[]

for _ in range(N):
    (t,d)=map(int,input().split())
    heapq.heappush(L,(-d,t))

LL=[]
sum=0
used=set()

for i in range(K):
    d,t=heapq.heappop(L)
    if t in used:
        heapq.heappush(LL,(-d,t))
    used.add(t)
    sum+=-d

ans=len(used)**2+sum

while L and LL:
    d,t=heapq.heappop(L)
    if t not in used:
        used.add(t)
        dd,_=heapq.heappop(LL)
        sum=sum-dd+(-d)
        ans=max(ans,len(used)**2+sum)

print(ans)

Solution (Python):
N,K = map(int,input().split())
dt = sorted(tuple(map(int,input().split()))[::-1] for _ in range(N))[::-1]
a = [] 
s = set()
ans,cur = 0,0
for i,(d,t) in enumerate(dt,1):
    if t in s:
        if i <= K:
            a.append(d)
            cur += d
    else:
        if i > K:
            if not a:
                break
            cur -= a.pop() 
        cur += d
        s.add(t)
    ans = max(ans,len(s)**2+cur) 
print(ans)

Solution (Python):
from collections import defaultdict
import heapq

def main():
	n, k = map(int, input().split())
	td = [0]*n
	group = defaultdict(list)
	for i in range(n):
		td[i] = list(map(int, input().split()))
		group[td[i][0]].append(td[i][1])

	grouplist = list(group.values())
	for g in grouplist:
		g.sort(reverse=True)
	grouplist.sort(key=lambda x: -x[0])

	non_maxes = []
	result = 0
	base = 0

	
	for i in range(min(len(grouplist), k)):
		bonus = (i+1)*(i+1)
		
		for j, basic in enumerate(grouplist[i]):
			
			if j == 0:
				if len(non_maxes) > k - (i+1):
					remove = heapq.heappop(non_maxes)
				else:
					remove = 0
				
				base += basic - remove
			elif len(non_maxes) < k - (i+1):
				heapq.heappush(non_maxes, basic)
				base += basic
			
			elif non_maxes and non_maxes[0] < basic:
				base += basic - non_maxes[0]
				heapq.heapreplace(non_maxes, basic)
		result = max(result, base+bonus)
	print(result)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heapify,heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    return


def B():
    return


def C():
    return


def D():
    n,k = LI()
    g = LIR(n)
    g.sort(key = lambda x:-x[1])
    f = [0 for i in range(n+1)]
    x = 0
    ans = 0
    c = []
    for i in range(k):
        ans += g[i][1]
        if not f[g[i][0]]:x+=1
        else:c.append(g[i][1])
        f[g[i][0]] += 1
    ans += x**2
    c.sort()
    c = deque(c)
    d = ans
    for i in range(k,n):
        if not c:
            break
        if f[g[i][0]]:continue
        d += g[i][1]-c.popleft()+2*x+1
        f[g[i][0]] = 1
        x += 1
        if d > ans:
            ans = d
    print(ans)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):

import sys, heapq


def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    group = {}
    for i in range(N):
        k = t[i]
        v = d[i]
        if k in group:
            group[k].append(v)
        else:
            group[k] = [v]
    groups = list(group.values())
    for g in groups:
        g.sort(reverse=True)
    groups.sort(reverse=True, key=lambda x: x[0])
    h = []
    ret = 0
    base = 0
    
    for i in range(min(len(groups), K)):
        g = groups[i]
        bonus = (i + 1) ** 2
        for j, v in enumerate(g):
            if j == 0:
                if len(h) > K - (i + 1):
                    remove = heapq.heappop(h)
                else:
                    remove = 0
                base = base - remove + v
            elif len(h) < K - (i + 1):
                heapq.heappush(h, v)
                base += v
            elif len(h) > 0 and h[0] < v:
                base += v - h[0]
                heapq.heapreplace(h, v)
            ret = max(ret, base + bonus)
            
            
            
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):
sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn

sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  
mt = len(sydic)  
ans = ot + mt ** 2
ci = 0
zi = 0
while 1:
    
    for i in range(ci, tn):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            ci = i + 1
            break
    else:
        break
    
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i + 1
            break
    else:
        break
    
    ans = max(ans, ot + mt ** 2)
print(ans)

Solution (Python):
from heapq import heappush, heappop
n, k =map(int, input().split())


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

LL=[]
sum = 0
s = set()
for i in range(k):
    d, t = heappop(L)
    if t in s:
        heappush(LL, (-d, t)) 
    s.add(t)
    sum+=-d

ans = len(s)**2+sum

while L and LL:
    d, t = heappop(L)
    if t not in s:
        s.add(t)
        dd, _ = heappop(LL)
        sum = sum -dd +(-d)
        ans = max(ans, len(s)**2+sum)
print(ans)