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):
from heapq import heappush, heappop

n, k = map(int, input().split())
c = []
for i in range(n):
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
f = sorted(c, key=lambda x:(x[1], x[0]), reverse=True)
donyoku = 0
donset = set()

notfirst =[]
for i in range(k):
    if f[i][0] not in donset:
        donset.add(f[i][0])
    else:
        heappush(notfirst, f[i][1])
    donyoku += f[i][1]
donyoku += len(donset)**2

candidate = []
candidateset = set()
donyokulength = len(donset)
for i in range(k, n):
    if f[i][0] not in donset:
        candidate.append(-f[i][1])
        candidateset.add(f[i][0])
        donset.add(f[i][0])

satili = [donyoku]
donyoku -= donyokulength**2
for i in range(len(candidateset)):
    if notfirst == []:
        break
    else:
        donyoku -= heappop(notfirst)
        donyoku += -heappop(candidate)
        donyoku += (donyokulength + i + 1) ** 2
        satili.append(donyoku)
    donyoku -= (donyokulength + i + 1) ** 2




print(max(satili))

Solution (Python):
from heapq import heapify,heappush,heappop
N,K=map(int,input().split())
sushi=[]
for i in range(N):
  t,d=map(int,input().split())
  sushi.append((d,t-1))
sushi.sort(key=lambda x:-x[0])
inf=float("inf")
oishisa=[-inf]*(N+1)
neta=[0]*N
heaps=[[] for i in range(N)]
S=[]
heapify(S)
for i in range(N):
  heapify(heaps[i])
a,k=0,0
for d,t in sushi[:K]:
  a+=d
  neta[t]+=1
  if neta[t]==1:
    k+=1
  heappush(heaps[t],d)

oishisa[k]=a
for i in range(N):
  if neta[i]>=2:
    d=heappop(heaps[i])
    heappush(S,(d,i))
for d,t in sushi[K:]:
  if len(S)==0:
    break
  if neta[t]==0:
    neta[t]+=1
    d_,t_=heappop(S)
    neta[t_]-=1
    if neta[t_]>=2:
      d__=heappop(heaps[t_])
      heappush(S,(d__,t_))
    heappush(heaps[t],d)
    oishisa[k+1]=oishisa[k]+d-d_
    k+=1
ans=0
for i in range(N+1):
  ans=max(oishisa[i]+i*i,ans)
print(ans)

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)
    new_scores = deque()
    new_scores.append(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
            new_score = new_scores[-1] + delta
            new_scores.append(new_score)

            distinct_set.add(comp[0])
    
    return max(new_scores)

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

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
td = [tuple(li()) for _ in range(n)]

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

kindset = set()
doublestack = []

ans = 0

for ti, di in td[:k]:
    if ti in kindset:
        doublestack.append((ti,di))
    
    else:
        kindset.add(ti)
        
    ans += di

ans += len(kindset) * len(kindset)
score = ans


for ti, di in td[k:]:
    if ti in kindset:
        continue
    
    
    if len(doublestack) == 0:
        break
    
    
    old_ti, old_di = doublestack.pop()    
    score = score - old_di + di + 2*len(kindset) + 1
    
    
    ans = max(ans, score)    
    kindset.add(ti)
    
    
print(ans)

Solution (Python):
N, K = [int(x) for x in input().split()]


s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)


m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)



kinds = len(m)

import itertools

acM = list(itertools.accumulate(m))
acAll2 = list(itertools.accumulate(all2))

ans = 0

for i in range(0, min(K, kinds)):
    
    
    
    t1 = acM[i]
    idx = K - i - 2
    t2 = acAll2[idx] if idx >= 0 and idx < len(acAll2)  else 0
    newAns = t1 + t2 + (i + 1) ** 2
    ans = max(ans, newAns)

print(ans)

pass

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop


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

maxs = []
for key in dic:
    dic[key].sort()
    maxs.append((dic[key].pop(), key))

maxs.sort(reverse=True)
queSize = 0
que = []
queScore = 0
defaultScore = 0
cnt = 0
ans = 0
for v, key in maxs:
    defaultScore += v + cnt * 2 + 1
    cnt += 1
    if cnt >= k:
        ans = max(ans, defaultScore)
        break
    for add in dic[key]:
        heappush(que, add)
        queSize += 1
        queScore += add
    while queSize > k - cnt:
        queScore -= heappop(que)
        queSize -= 1
    ans = max(ans, defaultScore + queScore)

print(ans)

Solution (Python):
from collections import defaultdict as dd
import heapq

n,k=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
l.sort(key=lambda x:-x[1])

sushi_types = set()
sushies = []
v=0

for i in range(k):
    t,d=l[i]
    v+=d
    if t in sushi_types:
        heapq.heappush(sushies,d)
    else:
        sushi_types.add(t)

remaining_sushi=dd(list)
for i in range(k,n):
    t,d=l[i]
    if not t in sushi_types:
        heapq.heappush(remaining_sushi[t],-d)

eat_candidate_sushi = []
for i in remaining_sushi.keys():
    if not i in sushi_types:
        heapq.heappush(eat_candidate_sushi,remaining_sushi[i][0])

sushi_kinds=len(sushi_types)
val=v
ans=v+sushi_kinds**2

for i in range(sushi_kinds+1,k+1):
    if sushies and eat_candidate_sushi:
        v-=heapq.heappop(sushies)
        v-=heapq.heappop(eat_candidate_sushi)
        ans=max(ans,v+i**2)
    else:
        break

print(ans)

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

inputs = []
priority_queue = []
queue = []
sets = set()

for _ in range(N):
    key, value = map(int, input().split())
    inputs.append((value, key))

inputs.sort(reverse=True) 

for i in range(K):
    value, key = inputs[i]
    if key in sets:
        queue.append(value)
    else:
        priority_queue.append(value)
        sets.add(key)

sum_priority_queue = sum(priority_queue)
sum_queue = sum(queue)
kinds = len(sets)
ans = sum_priority_queue + sum_queue + kinds ** 2
for i in range(K, N):
    if not queue:
        break
    value, key = inputs[i]
    if key in sets:
        continue
    sets.add(key)
    sum_queue -= queue.pop()
    sum_priority_queue += value
    kinds += 1
    ans = max(ans, sum_priority_queue + sum_queue + kinds ** 2)

print(ans)

Solution (Python):


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

e = [None for _ in range(N + 1)] 
t_kinds_count = 0 
rest_length = 0 

tops = [] 
c_tops = [0] 
rests = [] 
c_rests = [0] 

for _ in range(N):
    t, d = map(int, input().split())
    if e[t] is None:
        e[t] = []
        t_kinds_count += 1
    e[t].append(d)


for t in range(1, N + 1):
    if e[t] is None:
        continue
    e[t].sort(reverse=True)
    tops.append(e[t][0])
    rests.extend(e[t][1:])

tops.sort(reverse=True)
rests.sort(reverse=True)

s = 0
for tt in tops:
    s += tt
    c_tops.append(s)

s = 0
for rr in rests:
    s += rr
    c_rests.append(s)
    rest_length += 1

ans = 0
for yy in range(1, min(t_kinds_count, K) + 1):
    if 0 <= K - yy <= rest_length:
        ans = max(ans, c_tops[yy] + c_rests[K - yy] + yy * yy)






print(ans)

Solution (Python):
N,K=map(int,input().split())
b=[] 
 
for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
b.sort(key=lambda x:-x[1])
 
f=[0]*(N+1)
x=0
point=0
 
for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x
 
h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h = i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Solution (Python):
N, K = (int(i) for i in input().split())
L = []
for i in range(N):
    t,d = (int(i) for i in input().split())
    L.append((t,d))

L = sorted(L, key = lambda x:(x[0], -x[1]))
for i in range(N):
    if i == 0:
        ra = 0
        L[i] = (L[i][0], L[i][1], ra)
    else:
        if L[i][0] == L[i-1][0]:
            ra += 1
        else:
            ra = 0
        L[i] = (L[i][0], L[i][1], ra)

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

if N != K:
    kouho = L[:K]
    amari = L[K:]
else:
    kouho = L
    
nowval = len(set([sushi[0] for sushi in kouho]))
nowder = sum([sushi[1] for sushi in kouho])
point = nowval ** 2 + nowder

if N == K:
    print(point)
else:
    weaks = []
    for sushi in kouho:
        if sushi[2] > 0:
            weaks.append(sushi)
    weaks.reverse()
    kaburan = []
    for sushi in amari:
        if sushi[2] == 0:
            kaburan.append(sushi)
    
    ma = min(len(weaks), len(kaburan))
    newpoint = point
    if ma:
        for i in range(ma):
            newpoint = newpoint - weaks[i][1] + kaburan[i][1]
            newpoint = newpoint - nowval ** 2 + (nowval + 1) ** 2
            nowval += 1
            point = max(point, newpoint)
        print(point)
    else:
        print(point)

Solution (Python):
import sys
def 解():
    input = sys.stdin.readline
    N,K = [int(_) for _ in input().split()]
    aP = sorted([[int(_) for _ in input().split()] for _ in range(N)],key=lambda x:x[1],reverse=True)
    dS = set()
    aPK = aP[:K]
    for t,d in aPK:
        dS.add(t)
    dSall = dS.copy()
    for t,d in aP[K:]:
        dSall.add(t)
    iSall = len(dSall)

    iSum = sum(x[1] for x in aPK)
    i種類 = len(dS)
    iTotal = iSum + i種類**2
    if iSall == len(dS): 
        print(iTotal)
        exit()
    else: 
        
        dPK = {}
        for t,d in aPK:
            if t in dPK :
                dPK[t].append(d)
            else:
                dPK[t] = [d]
        vT = set()
        j = K - 1
        for nt,nd in aP[K:]:
            if i種類 == iSall:
                break
            if nt not in dS:
                
                for i in range(j,-1,-1):
                    t,d = aPK[i]
                    if t not in vT:
                        dPK[t].sort()
                        vT.add(t)
                    aT = dPK[t]
                    if 1 < len(aT):
                        iNewTotal = iSum - d + nd  + (i種類+1)**2
                        if iTotal < iNewTotal:
                            iTotal = iNewTotal
                        del dPK[t][0]
                        dPK[nt]=[nd]
                        aPK[i]=[nt,nd]
                        i種類 += 1
                        iSum = iSum -d +nd
                        dS.add(nt)
                        break
                j=i-1
        print(iTotal)
解()

Solution (Python):
import sys
def 解():
    input = sys.stdin.readline
    N,K = [int(_) for _ in input().split()]
    aP = sorted([[int(_) for _ in input().split()] for _ in range(N)],key=lambda x:x[1],reverse=True)
    dP = {}
    for t,d in aP:
        if t in dP:
            dP[t].append(d)
        else:
            dP[t] = [d]
    iSall = len(dP.keys())
    dS = set()
    aPK = aP[:K]
    for x in aPK:
        dS.add(x[0])
    iSum = sum(x[1] for x in aPK)
    i種類 = len(dS)
    iTotal = iSum + i種類**2
    if iSall == len(dS): 
        print(iTotal)
        exit()
    else: 
        
        dPK = {}
        for t,d in aPK:
            if t in dPK :
                dPK[t].append(d)
            else:
                dPK[t] = [d]
        vT = set()
        j = K - 1
        for nt,nd in aP[K:]:
            if i種類 == iSall:
                break
            if nt not in dS:
                
                for i in range(j,-1,-1):
                    t,d = aPK[i]
                    if t not in vT:
                        dPK[t].sort()
                        vT.add(t)
                    aT = dPK[t]
                    if 1 < len(aT):
                        iNewTotal = iSum - d + nd  + (i種類+1)**2
                        if iTotal < iNewTotal:
                            iTotal = iNewTotal
                        del dPK[t][0]
                        dPK[nt]=[nd]
                        aPK[i]=[nt,nd]
                        i種類 += 1
                        iSum = iSum -d +nd
                        dS.add(nt)
                        break
                j=i-1
        print(iTotal)
解()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    dt = sorted([LI()[::-1] for _ in range(n)], reverse=True)

    u = set()
    s = 0
    o = []
    for d,t in dt[:k]:
        if t in u:
            o.append(d)
        else:
            u.add(t)
        s += d
    r = s + len(u) ** 2
    oi = len(o) - 1
    for d,t in dt[k:]:
        if oi < 0:
            break
        if t in u:
            continue
        s -= o[oi]
        oi -= 1
        s += d
        u.add(t)
        tr = s + len(u) ** 2
        if r < tr:
            r = tr

    return r



print(main())

Solution (Python):
import sys
from collections import Counter
from operator import itemgetter
input = sys.stdin.readline

N, K = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(reverse=True, key=itemgetter(1))

selected = Counter()
ans = 0
stack = []

for t, d in TD[:K]:
    ans += d
    selected[t] += 1
    stack.append((t, d))
ans += len(selected) ** 2

tmp = ans
for t, d in TD[K:]:
    if t in selected:
        continue
    while stack:
        t0, d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2 * len(selected) + 1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)

Solution (Python):
def d_various_sushi(N, K, Param):
    import heapq

    
    sushi_parameter = sorted(Param, key=lambda x: x[1], reverse=True)
    sushi_invariably_chosen = []  
    candidate_reject = []  
    chosen_topping = set()  
    for i in range(K):
        t, d = sushi_parameter[i]
        if t not in chosen_topping:
            sushi_invariably_chosen.append(d)
            chosen_topping.add(t)
        else:
            heapq.heappush(candidate_reject, d)

    
    delicious_sum1 = sum(sushi_invariably_chosen)
    delicious_sum2 = sum(candidate_reject)
    topping_variety = len(chosen_topping)
    ans = delicious_sum1 + delicious_sum2 + topping_variety**2

    for i in range(K, N):
        if len(candidate_reject) == 0:
            break  

        t, d = sushi_parameter[i]
        if t in chosen_topping:
            
            continue

        
        delicious_sum2 -= heapq.heappop(candidate_reject)
        
        chosen_topping.add(t)
        delicious_sum1 += d
        topping_variety += 1

        ans = max(ans, delicious_sum1 + delicious_sum2 + topping_variety**2)
    return ans

N, K = [int(i) for i in input().split()]
Param = [[int(i) for i in input().split()] for j in range(N)]
print(d_various_sushi(N, K, Param))

Solution (Python):
N, K = map(int, input().split())
umai = {}
mazui = []
for _ in range(N):
    t, d = map(int, input().split())
    if t not in umai:
        umai[t] = d
    else:
        tmp = umai[t]
        if tmp < d:
            umai[t] = d
            mazui.append((t, tmp))
        else:
            mazui.append((t, d))

umai = sorted(umai.items(), key=lambda x: -x[1])
mazui = sorted(mazui, key=lambda x: -x[1])


umai_len = len(umai)
mazui_len = len(mazui)

acc_umai = [0 for _ in range(umai_len)]
acc_umai[0] = umai[0][1]
for i in range(umai_len - 1):
    acc_umai[i + 1] = acc_umai[i] + umai[i + 1][1]

acc_mazui = [0 for _ in range(mazui_len)]
if mazui_len > 0:

    acc_mazui[0] = mazui[0][1]
    for i in range(mazui_len - 1):
        acc_mazui[i + 1] = acc_mazui[i] + mazui[i + 1][1]
acc_mazui.insert(0, 0)

ans = []
for i in range(1, K + 1):
    if umai_len < i or mazui_len < K - i:
        continue
    ans.append(acc_umai[i - 1] + acc_mazui[K - i] + i ** 2)
print(max(ans))

Solution (Python):
from sys import exit

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

for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
b.sort(key=lambda x:-x[1])

f=[0]*(N+1)
x=0
point=0

for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x

h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h=i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Solution (Python):
from sys import exit

N,K=map(int,input().split())
a={} 
b=[] 

for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
    try:
        a[t].append(d)
    except KeyError:
        a[t]=[d]
b.sort(key=lambda x:-x[1])

f=[0]*(N+1)
x=0
point=0
pointsum=[]

for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x

h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h=i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Solution (Python):
N, K = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
 

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

 
baset = 0
ts = set()
ds = []
 
for t, d in xs[:K]:
    baset += d
    if not t in ts:
        ts.add(t)
    else:
        ds.append(d)
result = baset + len(ts)**2
r = result

for t, d in xs[K:]:
    if not ds:
        break
    if t not in ts:
        r += 2*len(ts) + 1
        r += d - ds.pop()
        ts.add(t)
        result = max(r,result)

print(result)

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

Solution (Python):
import heapq as h
I=lambda:list(map(int,input().split()))
n,k=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=v*2+1;v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+v*2+1-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Solution (Python):
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];q=[];v=i=T=A=0;l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Solution (Python):
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=i=T=A=0;l=[0]*-~n
for a,b in s:
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Solution (Python):
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=i=T=A=0;l=[0]*-~n
for a,b in s:
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Solution (Python):
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=T=A=0;l=[0]*-~n
for i,(a,b)in enumerate(s):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T)
print(A)

Solution (Python):



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

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


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


greedy = []
c=0
oisi = [0]*n
neta = [0]*n
ans = 0
for i in range(k):
    t_temp = td[i][0]
    d_temp = td[i][1]

    ans += d_temp
    if neta[t_temp] == 0:
        c+=1
        oisi[t_temp] = d_temp
        neta[t_temp] += 1
    else:
        if oisi[t_temp] > d_temp:
            greedy.append(d_temp)
        else:
            greedy.append(oisi[t_temp])
            oisi[t_temp] = d_temp



ans += c*c


amari=[]
for i in range(k,n):
    t_temp= td[i][0]

    if neta[t_temp] == 0:
        amari.append(td[i][1])
        neta[t_temp] += 1

greedy.sort(reverse=True)
amari.sort()




temp=ans
while(len(greedy)!= 0 and len(amari)!=0):
    a=greedy.pop()
    b=amari.pop()
    temp += b-a+2*c+1
    if ans < temp:
        ans = temp
    c+=1

print(ans)

Solution (Python):
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=A=0;l=[0]*-~n
for a,b in s[:k]:
 if l[a]:h.heappush(q,b)
 else:A+=z[v];v+=1
 l[a]=1;A+=b
T=A
for a,b in s[k:]:
 if l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1;A=max(A,T)
print(A)

Solution (Python):
import heapq
N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]


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


MAX_various = min(K, len(set([t for t, d in sushi])))


eat = []

various = set()

remain_sushi = []

score = 0

cnt = 0
for t, d in sushi:
    if (t not in various) and (cnt != MAX_various):
        score += d
        heapq.heappush(eat, d)
        various.add(t)
        cnt += 1
    else:
        remain_sushi.append([t, d])

score += len(various) ** 2


for t, d in remain_sushi[:K - MAX_various]:
    score += d
    heapq.heappush(eat, d)
remain_sushi = remain_sushi[K - MAX_various:]


ans = score
various = len(various)
for t, d in remain_sushi:
    add_ans = ans - eat[0] + d - (various ** 2) + (various - 1) ** 2
    if add_ans > ans:
        heapq.heapreplace(eat, d)
        ans = add_ans
        various -= 1

print(ans)

Solution (Python):
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind-1] + d[i] - tmp)
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Solution (Python):
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind-1] + d[i] - tmp)









for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Solution (Python):
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp





while q:
    kind += 1
    tmp = q.pop()
    for i in range(now, N):
        now += 1
        if t[i] not in s:
            s.add(t[i])
            sums.append(sums[kind-1] + d[i] - tmp)
            break
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Solution (Python):
N, K = map(int, input().split())
sushi_list = []
max_d = [0] * N
for i in range(N):
    t, d = map(int, input().split())
    sushi_list.append((t - 1, d))
    max_d[t - 1] = max(max_d[t - 1], d)

sushi_list.sort(key=lambda x: x[1], reverse=True)
good = []
for i in range(N):
    if max_d[sushi_list[i][0]] == sushi_list[i][1]:
        good.append(True)
        max_d[sushi_list[i][0]] = 0
    else:
        good.append(False)

s = sum([sushi[1] for sushi in sushi_list[:K]])
p = len(set([sushi[0] for sushi in sushi_list[:K]]))
ans = s + p**2
r = K - 1
l = K
while True:
    while r >= 0 and good[r]:
        r -= 1
    while l < N and not good[l]:
        l += 1
    if r < 0 or l >= N:
        break
    s = s - sushi_list[r][1] + sushi_list[l][1]
    p += 1
    ans = max(ans, s + p**2)
    r -= 1
    l += 1

print(ans)

Solution (Python):


from collections import Counter

N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))


ans += len(selected)**2


tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
print(ans)

Solution (Python):
from collections import Counter
N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))
ans += len(selected)**2

tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)

Solution (Python):
N,K=map(int,input().split())
t=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    t[i],d[i]=map(int,input().split())
D=dict()
for i in range(N):
    if not(t[i] in D):
        D[t[i]]=[]
    D[t[i]].append((d[i],i))
E=[0 for i in range(N)]
for key in D:
    D[key].sort(reverse=True)
    E[D[key][0][1]]=1
A=[]
B=[]
for i in range(N):
    if E[i]==1:
        A.append(d[i])
    else:
        B.append(d[i])
A.sort(reverse=True)
B.sort(reverse=True)
X=len(A)
Y=len(B)
S=[0 for i in range(X+1)]
T=[0 for i in range(Y+1)]
for i in range(X):
    S[i+1]=A[i]+S[i]
for i in range(Y):
    T[i+1]=B[i]+T[i]
L=[]
for i in range(1,K+1):
    if i<=X and K-i<=Y:
        L.append(S[i]+T[K-i]+i*i)
print(max(L))

Solution (Python):

from collections import deque
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])

used = set()
q = []
res = 0
kind = 0
for i in range(k):
    t,d = td[i]
    if t not in used:
        kind += 1
        used.add(t)
    else:
        q.append((t,d))
    res += d
res += kind**2
q = deque(sorted(q, key=lambda x:x[1]))

tmp = res
for i in range(k,n):
    if len(q)==0:
        break
    t2,d2 = td[i]
    if t2 in used:
        continue
    used.add(t2)
    t,d = q.popleft()

    r = tmp - d + d2
    r -= kind**2
    kind += 1
    r += kind**2
    res = max(res, r)
    tmp = r

print(res)