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 collections import Counter
N, K =  map(int, (input().split(' ')))
sushi = [tuple(map(int, input().split(' '))) for _ in range(N)]
all_sushi = sorted(sushi, key=lambda x: -x[1])
default_sushi = all_sushi[:K]
amari = all_sushi[K:]
len_amari = len(amari)
counter = Counter([i[0] for i in default_sushi])
result = []
def calc_value(sushi):
    return sum([i[1] for i in sushi]) + len(counter)**2

fs = []
def change_sushi(sushi):
    oishisa = sum([i[1] for i in sushi])
    fs.append(oishisa + len(counter)**2)
    amari_index = 0
    for s in sushi[::-1]:
        if counter[s[0]] >= 2:
            while amari_index < len_amari:
                a = amari[amari_index]
                amari_index += 1
                if a[0] not in counter:
                    counter[s[0]] -= 1
                    counter[a[0]] += 1
                    oishisa = oishisa - s[1] + a[1]
                    fs.append(oishisa + len(counter)**2)
                    break
    print(max(fs))
    exit()
            
    
def get_sushi(sushi):
    
    changed_sushi = change_sushi(sushi)
    
        
        
    

get_sushi(default_sushi)

Solution (Python):
n,m = map(int,input().split())
a = []
for i in range(n):
    r,t = map(int,input().split())
    a.append([t,r])
a.sort(reverse = True)
d = {}
cd = []
dp = 0
x = 0

for i in range(m):
    z,c = a[i]
    dp += z
    if c in d:
        cd.append(z)
    else:
        d[c] = z
        x += 1
cd.sort(reverse = True)
ans = dp + x**2
c = ans

for i in range(m,n):
    if len(cd) == 0:
        break
    z,v = a[i]
    if v in d:
        continue
    d[v] = z
    x += 1
    c = c - cd.pop()+z+2*x-1
    if c > ans:
        ans = c
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = []
for i in range(n):
    r,t = map(int,input().split())
    a.append((t,r))
a.sort(reverse = True)
d = {}
cd = []
dp = 0
x = 0

for i in range(m):
    z,c = a[i]
    dp += z
    if c in d:
        cd.append(z)
    else:
        d[c] = z
        x += 1
cd.sort(reverse = True)
ans = dp + x**2
c = ans

for i in range(m,n):
    if len(cd) == 0:
        break
    z,v = a[i]
    if v in d:
        continue
    d[v] = z
    x += 1
    c = c - cd.pop()+z+2*x-1
    if c > ans:
        ans = c
print(ans)

Solution (Python):
N, K = map(int, input().split())
best = [0] * N
not_best = []
for _ in range(N):
    t, d = map(int, input().split())
    if best[t-1] != 0:
        not_best.append(min(d, best[t-1]))
    best[t-1] = max(d, best[t-1])
best = [x for x in best if x != 0]
best.sort(reverse=True)
not_best.sort(reverse=True)
acc_best = [0] * (N + 1)
acc_not_best = [0] * (N + 1)
for i in range(len(best)):
    acc_best[i+1] = acc_best[i] + best[i]
for i in range(len(not_best)):
    acc_not_best[i+1] = acc_not_best[i] + not_best[i]
cand = []
for x in range(1, K+1):
    if x > len(best):
        break
    if K - x > len(not_best):
        continue
    cand.append(acc_best[x] + acc_not_best[K-x] + x**2)
print(max(cand))

Solution (Python):
import collections

index = 0

def maxsushi(sushi_list,eaten_sushi):
    global index
    max_val = [0,0]
    for i in range(index,len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Solution (Python):


import sys


n,k = map(int, input().split())
td_mx = {}
td = []
for _ in range(n):
  t,d = map(int, input().split())
  if t not in td_mx:
    td_mx[t] = d
  elif td_mx[t] < d:
    td.append(td_mx[t])
    td_mx[t] = d
  else:
    td.append(d)
td = sorted(td, key=lambda x:-x)
td_mx = sorted(td_mx.values(), key=lambda x:-x)


csum = [0]
csum_mx = [0]
for i in range(len(td)):
  csum.append(csum[-1] + td[i])
for i in range(len(td_mx)):
  csum_mx.append(csum_mx[-1] + td_mx[i])



ans = 0
for i in range(1,k+1):
  if i <= len(csum_mx)-1 and k-i <= len(csum)-1:
    ans = max(ans, csum_mx[i] + csum[k-i] + i*i)
print(ans)

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

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

Q = []
used = {}
dsum = 0
for i in range(k):
    d, t = heappop(H)
    if t not in used:
        used[t] = 1
    else:
        heappush(Q, (- d, t))
    dsum += - d
    
ans = len(used) ** 2 + dsum
        






while H and Q:
    d, t = heappop(H)
    if t not in used:
        used[t] = 1
        m, _ = heappop(Q)
        dsum = dsum - m - d
        ans = max(ans, len(used) ** 2 + dsum)
        
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    """
    N個の寿司があり、それぞれの寿司には
    「ネタ」ti
    「おいしさ」di
    のパラメータが設定されています。 
    あなたはこの N個の寿司の中から K個を選んで食べようとしています。
    この時のあなたの「満足ポイント」は、以下のようにして計算されます。

    「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
    「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
    「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を xとしたとき、x ∗ x である。

    あなたは、「満足ポイント」をできるだけ大きくしたいです。
    この時の「満足ポイント」の値を求めてください。

    1 ≦ K  ≦ N ≦ 10^5
    1 ≦ ti ≦ N
    1 ≦ di ≦10^9

    nCk の組合せ: 10^5 C 10^5/2 => TLE
    DP ?
        1-Nまで, 食べる食べないによるスコア
        食べたとして種類数xとして種類は別途持っておく？
        →二次元配列は無理っぽそう, 10^5 * 10^5 = 10^10
        MAX時の種類だけ持って、１次元にする
        K までになっているかの判定
        →Nとは別に持たないといけない
    """
    N, K = map(int, input().split())
    td = [
        list(map(int, input().split()))
        for _ in range(N)
    ]
    ans = editorial(N, K, td)
    print(ans)


def editorial(N, K, td):
    td = sorted(td, key=lambda x: -x[1])
    c = defaultdict(int)
    d_sum = 0
    
    td_not_first = []
    for t, d in td[:K]:
        if c[t] > 0:
            td_not_first.append(d)
        c[t] += 1
        d_sum += d

    t_sum = len(c)
    ans = d_sum + t_sum ** 2

    for t, d in td[K:]:
        
        if not td_not_first:
            return ans
        
        if c[t] > 0:
            continue

        c[t] += 1
        d_sum += -td_not_first.pop() + d
        t_sum += 1
        ans = max(ans, d_sum + t_sum ** 2)

    return ans
    


if __name__ == '__main__':
    main()

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

over_stock = []
type_set = set()

for t_i, d_i in t_and_d[:K]:
    if t_i in type_set:
        over_stock += [d_i]
    else:
        type_set.add(t_i)

x = len(type_set)
point = sum([d for t, d in t_and_d[:K]]) + x ** 2
point_max = point

for t_i, d_i in t_and_d[K:]:
    if over_stock:
        if t_i in type_set:
            continue
        else:
            diff = (x + 1) ** 2 - x ** 2 + d_i - over_stock.pop()
            type_set.add(t_i)
            x += 1
            point += diff
            point_max = max(point_max, point)

print(point_max)

Solution (Python):
n, k = [int(item) for item in input().split()]
sushi = [[int(item) for item in input().split()] for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse = True)

kind = set()
changeable = []

points = 0
for i in range(k):
  points += sushi[i][1]
  if sushi[i][0] in kind:
    changeable.append(sushi[i][1])
  else:
    kind.add(sushi[i][0])

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

for i in range(k, n):
  if not changeable:
    break
  if sushi[i][0] not in kind:
    kind.add(sushi[i][0])
    points += sushi[i][1] - (len(kind)-1)**2 + len(kind)**2 - changeable.pop()
    ans = max(ans, points)

print(ans)

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


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


point = 0
neta_set = set()
removable_idx = list()
for i in range(K):
    s = sushi[i]
    point += s[1]
    if s[0] not in neta_set:
        neta_set.add(s[0])
    else:
        removable_idx.append(i)
point += len(neta_set) **2
max_point = point


for s in sushi[K:]:
    if len(removable_idx) == 0:
        break
    if s[0] in neta_set:
        continue
    idx = removable_idx[-1]
    count = len(neta_set)
    point += s[1] - sushi[idx][1]
    point += (count + 1) ** 2 - count ** 2
    neta_set.add(s[0])
    removable_idx = removable_idx[:-1]

    if point > max_point:
        max_point = point
print(max_point)

Solution (Python):
import heapq as pq
N,K = map(int,input().split(" "))
priority_que = []
t,d= [0]*N,[0]*N
sushi_max = [-1] * N
cnt = [0] * N

for i in range(N):
    t[i],d[i] = map(int,input().split(" "))
    sushi_max[t[i]-1] = max(sushi_max[t[i]-1],d[i])

t ,d= zip(*sorted(zip(t,d),reverse=True,key=lambda x: x[1]))
ans = 0
for i in range(K):
    cnt[t[i]-1] += 1
    sushi_max[t[i]-1] = -1
    pq.heappush(priority_que,(d[i],t[i]))
    ans += d[i]

sz = len(list(filter(lambda x: x > 0,cnt)))
ans += (sz * sz)

sushi_max = sorted([ (val,idx) for idx,val in enumerate(sushi_max) ],reverse=True,key=lambda x:x[0])
idx = 0
cur = ans
while len(priority_que) > 0 and sushi_max[idx][0] != -1:
    minValue,minIdx = pq.heappop(priority_que)
    if cnt[minIdx-1] == 1:
        continue
    cur += ( (sz+1)*(sz+1) - (sz*sz) + sushi_max[idx][0] - minValue )
    cnt[minIdx-1] -= 1
    sz += 1
    idx += 1
    ans = max(cur,ans)
print(ans)

Solution (Python):
import heapq as pq
N,K = map(int,input().split(" "))
td = []
sushi_max = [-1] * N
for i in range(N):
    t,d = map(int,input().split(" "))
    td.append((d,t))
    sushi_max[t-1] = max(sushi_max[t-1],d)

td.sort(reverse=True,key=lambda x:x[0])
cnt = [0] * N
que = []
ans = 0
for i in range(K):
    cnt[td[i][1]-1] += 1
    sushi_max[td[i][1]-1] = -1
    pq.heappush(que,td[i])
    ans += td[i][0]

sz = len(list(filter(lambda x: x > 0,cnt)))
ans += (sz*sz)

sushi_max = sorted([ (val,idx) for idx,val in enumerate(sushi_max) ],reverse=True,key=lambda x:x[0])
idx = 0
cur = ans
while len(que) > 0 and sushi_max[idx][0] != -1:
    minValue,minIdx = pq.heappop(que)
    if cnt[minIdx-1] == 1:
        continue
    cur -= minValue
    cur -= (sz*sz)
    cnt[minIdx-1] -= 1
    cnt[sushi_max[idx][1]-1] += 1
    cur += (sushi_max[idx][0] + (sz+1)*(sz+1))
    sz += 1
    idx += 1
    ans = max(cur,ans)
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, TD):
    TD.sort(key=lambda x: x[1], reverse=True)

    c = Counter()
    base = 0
    rc = []
    for i in range(K):
        t, k = TD[i]
        c[t] += 1
        base += k
        if c[t] > 1:
            rc.append((t, k))

    mi = i
    ans = base + len(c)**2
    while True:
        if len(rc) == 0:
            break
        rt, rk = rc.pop()
        for i in range(mi+1, len(TD)):
            if TD[i][0] not in c:
                c[TD[i][0]] += 1
                c[rt] -= 1
                base -= rk
                base += TD[i][1]
                mi = i
                ans = max(ans, base + len(c)**2)
                break

        else:
            break
    return ans


def main():
    
    N, K = read_int_n()
    TD = [read_int_n() for _ in range(N)]
    print(slv(N, K, TD))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, TD):
    TD.sort(key=lambda x: x[1], reverse=True)

    c = Counter()
    base = 0
    rc = []
    for i in range(K):
        t, k = TD[i]
        c[t] += 1
        base += k
        if c[t] > 1:
            rc.append((t, k))

    mi = i
    ans = [base + len(c)**2]
    while True:
        if len(rc) == 0:
            break
        rt, rk = rc.pop()
        for i in range(mi+1, len(TD)):
            if TD[i][0] not in c:
                c[TD[i][0]] += 1
                c[rt] -= 1
                base -= rk
                base += TD[i][1]
                mi = i
                ans.append(base + len(c)**2)
                break

        else:
            break
    return max(ans)


def main():
    
    N, K = read_int_n()
    TD = [read_int_n() for _ in range(N)]
    print(slv(N, K, TD))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, TD):
    TD.sort(key=lambda x: x[1], reverse=True)

    c = Counter()
    base = 0
    rc = []
    for i in range(K):
        t, k = TD[i]
        c[t] += 1
        base += k
        if c[t] > 1:
            rc.append((t, k))

    mi = i
    ans = [base + len(c)**2]
    while True:
        if len(rc) == 0:
            break
        rt, rk = rc.pop()
        cc = len(c)
        d = (cc+1)**2 - cc**2
        for i in range(mi+1, len(TD)):
            if TD[i][0] not in c:
                c[TD[i][0]] += 1
                c[rt] -= 1
                base -= rk
                base += TD[i][1]
                mi = i
                ans.append(base + len(c)**2)
                break

        else:
            break
    return max(ans)


def main():
    
    N, K = read_int_n()
    TD = [read_int_n() for _ in range(N)]
    print(slv(N, K, TD))


if __name__ == '__main__':
    main()

Solution (Python):
def various_sushi(N: int, K: int, TD: list) -> int:
    _TD = sorted(TD, key=lambda x: x[1], reverse=True)

    tops, others = [], []
    tops_sum, others_sum = 0, 0
    kind = set()
    res = 0
    q = []
    for t, d in _TD[:K]:
        if t not in kind:
            kind.add(t)
        else:
            q.append(d)
        res += d

    max_d = res + len(kind) ** 2
    temp = max_d
    count = len(q)
    for t, d in _TD[K:]:
        if count == 0:
            break
        if t not in kind:
            temp += -q.pop() + d + len(kind) * 2 + 1
            kind.add(t)
            max_d = max(max_d, temp)
            count -= 1

    return max_d


if __name__ == "__main__":
    N, K = [int(s) for s in input().split()]
    TD = [tuple(int(s) for s in input().split()) for _ in range(N)]

    ans = various_sushi(N, K, TD)
    print(ans)

Solution (Python):
from collections import deque
n, k = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]
res = 0
td.sort(key = lambda x:-x[1])
kind = set()
queue = deque()
for t, d in td[:k]:
    if t in kind:
        queue.append(d)
    else:
        kind.add(t)
    res += d
ans = res + len(kind)**2
point = ans
count = len(queue)
for t, d in td[k:n]:
    if count == 0:
        break
    if not t in kind:
        point += -queue.pop() + d + len(kind) * 2 + 1
        kind.add(t)
        ans = max(ans, point)
        count -= 1
print(ans)

Solution (Python):
N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,k=map(int,input().split())
Sushi=[list(map(int,input().split())) for i in range(n)]
Sushi=sorted(Sushi,key=lambda x: x[1],reverse=True)
ans=0
A=[]
kind=set()
for t,d in Sushi[:k]:
    ans+=d
    if t in kind:
        A.append(d)
    else:
        kind.add(t)
ans+=len(kind)**2
tmp=ans
for t,d in Sushi[k:]:
    if not A:
        break
    if not t in kind:
        tmp+=d-A.pop()+2*len(kind)+1
        kind.add(t)
        ans=max(ans,tmp)
print(ans)

Solution (Python):
from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

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

p = len(s)
q = len(t) - 1

if q < 0:
    print(ans[0] + k * k)
    exit()

v = []
for i in range(k, n):
    if a[i][0] not in s:
        s.add(a[i][0])
        v.append(a[i][1])

ans[0] += p * p
d = 0

for x in v:
    ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
    p += 1
    d += 1
    q -= 1
    if q < 0:
        break

print(max(ans))

Solution (Python):
N,K=map(int,input().split())
TD=[[int(j) for j in input().split()] for i in range(N)]
TD=sorted(TD,key=lambda x:-x[1])
point=0
stack=[]
kind=set()
for t,d in TD[:K]:
    point+=d
    if t in kind:stack.append(d)
    else:kind.add(t)
point=point+len(kind)**2
ans=point
for t,d in TD[K:]:
    if not stack:break
    if not t in kind:
        point+=d-stack.pop()+2*len(kind)+1
        kind.add(t)
        ans=max(ans,point)
print(ans)

Solution (Python):
from heapq import heappush, heappop

N, K = map(int, input().split(' '))
h = []
for _ in range(N):
    t, d = map(int, input().split(' '))
    heappush(h, (-d, t))

dsum = 0
used = {}
q = []
for _ in range(K):
    d, t = heappop(h)
    if t not in used:
        used[t] = 1
    else:
        heappush(q, (-d, t))
    dsum += -d
res = len(used)**2 + dsum

while h and q:
    d, t = heappop(h)
    if t not in used:
        used[t] = 1
        m, _ = heappop(q)
        dsum = dsum - m - d
        res = max(res, len(used)**2 + dsum)
print(res)

Solution (Python):
n, k = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(n)]

td = sorted(td, key = lambda x: x[1], reverse = True)
eat_types = set()
sushi_dup = []
value = 0
for t, d in td[:k]:
    if not t in eat_types:
        eat_types.add(t)
    else:
        sushi_dup.append(d)
    value += d

ans = value + len(eat_types)**2
for t, d in td[k:]:
    if len(sushi_dup) == 0:
        break
    
    if t in eat_types:
        continue
    else:
        eat_types.add(t)
        r = sushi_dup.pop()
        value += d - r
        ans = max(ans, value + len(eat_types)**2)
print(ans)

Solution (Python):
N,K = map(int,input().split())
lis = []
val = 0
ans = 0
s = set()
dub = []

for _ in range(N):
    lis.append(tuple(map(int,input().split())))

lis = sorted(lis,key=lambda x: x[1],reverse=True)

for t,v in lis[:K]:

    if t in s:
        dub.append(v)
    s.add(t)
    val += v

ans = val + len(s) ** 2

for t,v in lis[K:]:
    if len(dub) == 0:
        break
    if t in s:
        continue

    s.add(t)
    r = dub.pop()
    val += v - r
    ans = max(ans,val+len(s) ** 2)

print(ans)

Solution (Python):

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

sushi = sorted(list(map(int, input().split()))[::-1] for i in range(n))[::-1]
s = set()

q = []
kiso = 0
for i in range(k):
    d, t = sushi[i]
    if t in s:
        q.append(d)
    else:
        s.add(t)
    kiso += d
ans = kiso + len(s)**2


i = k
while i < n and q:
    d, t = sushi[i]
    if t not in s:
        s.add(t)
        kiso += -q.pop()+d
        ans = max(ans, kiso+len(s)**2)
        continue
    i+=1
print(ans)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
def main():
    n,k = map(int, input().split())
    sushi = [tuple(map(int, input().split())) for _ in range(n)]
    sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
    species = set()
    val = 0
    dup = []
    
    for t,d in sushi[:k]:
        
        if t in species:
            dup.append(d)
        species.add(t)
        val += d
    ans = val + len(species)**2

    for t,d in sushi[k:]:
        if len(dup)==0:
            break
        
        
        if t in species:
            continue
        species.add(t)
        removal = dup.pop()
        val += d - removal
        ans = max(ans, val + len(species)**2)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

ans=0
neta=set([])
rep_neta=[]

for i in range(K):
    a,b=TD[i]
    if not (a in neta):
        neta.add(a)
        ans+=b
    else:
        ans+=b
        rep_neta.append(b)

ans+=len(neta)**2

cnt=ans

for i in range(K,N):
    if len(rep_neta) == 0 :
        break
    else:
        a,b=TD[i]
        if not (a in neta):
            cnt+=2*len(neta)+1
            cnt+=b-rep_neta.pop(-1)
            neta.add(a)
            ans=max(ans,cnt)

print(ans)

Solution (Python):
N, K = [int(x) for x in input().split()]
td = sorted([[int(x) for x in input().split()] for _ in range(N)],
            key=lambda x: x[1], reverse=True)
INF = 10**9


first = []
second = []
kind = set()
for i in range(K):
    if td[i][0] not in kind:
        first.append(td[i])
        kind.add(td[i][0])
    else:
        second.append(td[i])

yummy = sum([x[1] for x in first + second])
best_ans = yummy + len(kind)**2

for k in range(K, N):
    if len(second) == 0:
        break
    if td[k][0] in kind:
        continue

    a = second.pop(-1)
    yummy -= a[1]
    kind.add(td[k][0])
    first.append(td[k])
    yummy += td[k][1]
    ans = yummy + len(kind)**2
    
    if best_ans < ans:
        best_ans = ans
print(best_ans)

Solution (Python):



import sys
input = sys.stdin.readline

def main():
    N, K = list(map(int, input().split()))
    l = []
    for _ in range(N):
        t, d = list(map(int, input().split()))
        l.append((d, t))
    l.sort(reverse=True)
    first = []
    second = []
    t_set = set()
    for k in range(K):
        if l[k][1] not in t_set:
            first.append(l[k])
            t_set.add(l[k][1])
        else:
            second.append(l[k])
    yummy = sum(e[0] for e in first) + sum(e[0] for e in second)
    best_ans = yummy + len(t_set)**2
    for k in range(K, N):
        if len(second) == 0:
            break
        if l[k][1] in t_set:
            continue
        sushi = second.pop(-1)
        yummy -= sushi[0]
        yummy += l[k][0]
        t_set.add(l[k][1])
        first.append(l[k])
        ans = yummy + len(t_set)**2
        if ans  > best_ans:
            best_ans = ans
    print(best_ans)


if __name__ == '__main__':
    main()

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

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

D = []
T = {}
d = 0

for i in range(K):
  D.append(td[i])
  d += td[i][1]
  t = td[i][0]
  if t in T:
    T[t] += 1
  else:
    T[t] = 1

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

cnt = 0
flag = False
Ans = d + pow(len(T), 2)
for i in range(K, N):
  if td[i][0] in T:
    continue
  while T[D[cnt][0]] == 1:
    cnt += 1
    if cnt == K:
      flag = True
      break
  if flag:
    break

  T[td[i][0]] = 1
  T[D[cnt][0]] -= 1
  d -= D[cnt][1] - td[i][1]
  
  t = d + pow(len(T), 2)
  if Ans < t:
    Ans = t
  cnt += 1
  if cnt == K:
    break

print(Ans)

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

T = 0
neta = set()
doublecounts = []
ans = []

for i in range(K):
    T += TD[i][1]    
    if not(TD[i][0] in neta):    
        neta.add(TD[i][0])       
    else:      
        doublecounts.append(TD[i][1])    
            
ans.append(T+len(neta)**2)

for i in range(K,N):
    if(len(doublecounts)==0):
        break
    if not(TD[i][0] in neta):
        T -= doublecounts.pop(-1)
        T += TD[i][1]
        neta.add(TD[i][0])   
        ans.append(T+len(neta)**2)
print(max(ans))

Solution (Python):
from collections import deque


def main():
    N, K = map(int, input().split())
    sushis = [None] * N
    for i in range(N):
        t, d = map(int, input().split())
        sushis[i] = (t, d)
    sushis.sort(key=lambda a: (-a[1], a[0]))
    tmp = 0
    types = set()
    stack = deque()
    ans = 0
    for i in range(len(sushis)):
        t, d = sushis[i]
        if i < K:
            if t in types:
                stack.append(d)
            types.add(t)
            tmp += d
        else:
            if t not in types and len(stack):
                types.add(t)
                tmp += d
                tmp -= stack.pop()
        ans = max(ans, tmp + len(types)**2)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

sushis = sorted(sushis, key=lambda x: (x[1], x[0]), reverse=True)

p = 0


def calcPoint(selected_sushis):
    p = 0
    vari = set()
    for i, v in selected_sushis:
        vari.add(i)
        p += v
    p += len(vari)**2
    return p, vari


selected = sushis[:K]
unSelected = sushis[K:]

p, vari = calcPoint(selected)
cand = [p]

va = len(vari)
v = [0]*(N+1)
for i, _ in selected:
    v[i] += 1

can_del = []
for i, d in reversed(selected):
    if v[i] >= 2:
        v[i] -= 1
        can_del.append(d)

can_in = []
for i, d in unSelected:
    if not i in vari:
        vari.add(i)
        can_in.append(d)


for od, nd in zip(can_del, can_in):
    nextp = p-od+nd-(va)**2+(va+1)**2
    p = nextp
    cand.append(p)
    va += 1
print(max(cand))

Solution (Python):
n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))


li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)
oishisa=sum([li[i][1] for i in range(k)])
score=oishisa+s1**2


li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
for i in range(s1+1,s2+1):
    oishisa=oishisa+best_list[i-1][1]-not_best_list[k-i][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)