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.



Sample input:
5 3
1 9
1 7
2 6
2 5
3 1


Sample output:
26

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
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
    #print(groups)
    for i, g in enumerate(groups):
        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, g[j])
                base += g[j]
            elif h[0] < v:
                base = base - h[0] + v
                heapq.heapreplace(h, v)
            ret = max(ret, base + bonus)
            #print(h)
            #print("bonus : %d, base : %d, ret : %d" % (bonus, base, ret))
            #print(' --- ')
    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))  # type: int
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

T=[]
D=[]

#入力を受け取る
for n in range(N):
    t, d=map(int, input().split())
    T.append(t)
    D.append(d)

#まず、寿司リストを作って大きい順にソートする。
sushi_list=[[D[n],T[n]] for n in range(N)]
sushi_list.sort(reverse=True)

#初期スコアの計算
score=0
used=[0 for n in range(N+1)]
num_unique=0
for k in range(K):
    d=sushi_list[k][0]
    t=sushi_list[k][1]
    used[t]+=1
    score+=d
    if used[t]==1:
        num_unique+=1
score+=num_unique*num_unique

#情勢を見て、より良いものに交換して行く。
add=0
rem=0
position=K-1
x=num_unique
for k in range(K,N):
    d=sushi_list[k][0]
    t=sushi_list[k][1]
    if used[t]==0:
        add+=d
        num_unique+=1
        used[t]+=1
        while used[sushi_list[position][1]]<=1:
            position-=1
        d_=sushi_list[position][0]
        t_=sushi_list[position][1]
        rem+=d_
        used[t_]-=1
        tmp_score=score+add-rem+num_unique*num_unique-x*x
        if score<tmp_score:
            score=tmp_score
            add=0
            rem=0
            x=num_unique
print(score)

Submission status: Runtime Error

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

T=[]
D=[]

#入力を受け取る
for n in range(N):
    t, d=map(int, input().split())
    T.append(t)
    D.append(d)

#まず、寿司リストを作って大きい順にソートする。
sushi_list=[[D[n],T[n]] for n in range(N)]
sushi_list.sort(reverse=True)

#初期スコアの計算
score=0
used=[0 for n in range(N)]
num_unique=0
for k in range(K):
    d=sushi_list[k][0]
    t=sushi_list[k][1]
    used[t]+=1
    score+=d
    if used[t]==1:
        num_unique+=1
score+=num_unique*num_unique

#情勢を見て、より良いものに交換して行く。
add=0
rem=0
position=K-1
x=num_unique
for k in range(K,N):
    d=sushi_list[k][0]
    t=sushi_list[k][1]
    if used[t]==0:
        add+=d
        num_unique+=1
        used[t]+=1
        while used[sushi_list[position][1]]<=1:
            position-=1
        d_=sushi_list[position][0]
        t_=sushi_list[position][1]
        rem+=d_
        used[t_]-=1
        tmp_score=score+add-rem+num_unique*num_unique-x*x
        if score<tmp_score:
            score=tmp_score
            add=0
            rem=0
            x=num_unique
print(score)

Submission status: Runtime Error

Solution code:
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:]
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 True:
                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):
    #result.append(calc_value(sushi))
    changed_sushi = change_sushi(sushi)
    #if not changed_sushi:
        #print(max(result))
        #return
    #get_sushi(changed_sushi)

get_sushi(default_sushi)

Submission status: Runtime Error

Solution code:
import heapq as hp
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
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:
        hp.heappush(cd,z)
    else:
        d[c] = z
        x += 1
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 - hp.heappop(cd)+d+2*x-1
    if c > ans:
        ans = c
print(ans)

Submission status: Runtime Error

Solution code:
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

if over_stock:
    for t_i, d_i in t_and_d[K:]:
        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)

Submission status: Runtime Error

Solution code:
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

if not over_stock:
    print(point)
    quit()

for t_i, d_i in t_and_d[K:]:
    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)

Submission status: Runtime Error

Solution code:
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_history = [point]

if not over_stock:
    print(point)
    quit()

for t_i, d_i in t_and_d[K:]:
    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_history.append(point)

print(max(point_history))

Submission status: Runtime Error

Solution code:
from collections import Counter
n, k = list(map(int, input().split(' ')))
t = []
d = []
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    t.append(a)
    d.append(b)

c = list(range(k))
ct = Counter(t[i] for i in c)
for i in range(k, n):
    for j in range(k):
        if d[i] > d[c[j]]:# or t[i] != t[c[j]]:
            c[j] = i
print(point(c))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(n)]
l = sorted(l,key=lambda x:-x[1])
unique = []
remove = []
ans = 0
for i in range(n):
    if i<k:
        ans += l[i][1]
        if l[i][0] in unique:
            remove.append(l[i][1])
        unique.append(l[i][0])
        continue
    if remove==[]:
        break
    if i==k:
        ans2 = ans
        unique2 = unique.copy()
        remove.sort()
        remove = remove[::-1]
    if not l[i][0] in unique:
        ans2 += l[i][1]
        ans2 -= remove.pop()
        unique2.append(l[i][0])
print(max(ans+len(set(unique))**2, ans2+len(set(unique2))**2))

Submission status: Runtime Error

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


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

def find_next(start, curr, point, tlist, tcount):
    if start == N:
        return [point, curr]
    max_c = curr
    max_p = point
    for s in sushi[start:]:
        if tlist[s[0]] > 0:
            continue
        for ri in range(len(curr) - 1, -1, -1):
            r = curr[ri]
            if tlist[r[0]] >= 2:
                c2 = [c for c in curr]
                t2 = [t for t in tlist]
                del c2[ri]
                c2.append(s)
                t2[r[0]] -= 1
                t2[s[0]] = 1
                p2 = point - r[1] + s[1] + (tcount + 1) * (tcount + 1) - tcount * tcount
                np, pc = find_next(start + 1, c2, p2, t2, tcount + 1)

                if np > max_p:
                    max_p = np
                    max_c = pc
                break
    return [max_p, max_c]

result = sushi[0: K]
type_count = [0] * (N + 1)

for r in result:
    type_count[r[0]] += 1
type_num = 0
for t in type_count:
    if t > 0:
        type_num += 1
point = type_num * type_num
for r in result:
    point += r[1]
ans_p, ans_c = find_next(K, result, point, type_count, type_num)

print(ans_p)

Submission status: Runtime Error

Solution code:
import math

N, K = [int(i) for i in input().split()]
tdList = [[int(i) for i in input().split()] for _ in range(N)]

type_sorted_tdList = sorted(tdList, key=lambda x: x[0], reverse=False)
sorted_tdList = sorted(tdList, key=lambda x: x[1], reverse=True)

ans = 0
iniList = []
typeDict = {}
count = 0
for i, td in enumerate(sorted_tdList):
    addFlag = False
    if td[0] not in typeDict:
        addFlag = True
        typeDict[td[0]] = 1
    else:
        if count < K - type_sorted_tdList[-1][0]:
            addFlag = True
            typeDict[td[0]] += 1
            count += 1
    if addFlag:
        ans += td[1]
        iniList.append(td)
        rmTd = sorted_tdList.pop(i)
        sorted_tdList.insert(0, rmTd)
    if len(iniList) == K:
        break

ans += math.pow(2, len(typeDict))
del sorted_tdList[:K]

for td in iniList[::-1]:
    diff = 0
    typeDict[td[0]] -= 1
    if typeDict[td[0]] == 0:
        typeDict.pop(td[0])
        diff -= math.pow(2, (len(typeDict) + 1)) - math.pow(2, len(typeDict))
    diff -= td[1]
    if len(sorted_tdList) > 0:
        diff += sorted_tdList[0][1]
        sorted_tdList.pop(0)
    if diff > 0:
        ans += diff
    else:
        break

print(int(ans))

Submission status: Runtime Error

Solution code:
import math

N, K = [int(i) for i in input().split()]
tdList = [[int(i) for i in input().split()] for _ in range(N)]

type_sorted_tdList = sorted(tdList, key=lambda x: x[0], reverse=False)
sorted_tdList = sorted(tdList, key=lambda x: x[1], reverse=True)

ans = 0
iniList = []
typeDict = {}
count = 0
for i, td in enumerate(sorted_tdList):
    addFlag = False
    if td[0] not in typeDict:
        addFlag = True
        typeDict[td[0]] = 1
        ans += td[1]
    else:
        if count < K - type_sorted_tdList[-1][0]:
            addFlag = True
            typeDict[td[0]] += 1
            count += 1
    if addFlag:
        iniList.append(td)
        rmTd = sorted_tdList.pop(i)
        sorted_tdList.insert(0, rmTd)
    if len(iniList) == K:
        break

ans += math.pow(2, len(typeDict))
del sorted_tdList[:K]

for td in iniList[::-1]:
    diff = 0
    typeDict[td[0]] -= 1
    if typeDict[td[0]] == 0:
        typeDict.pop(td[0])
        diff -= math.pow(2, (len(typeDict) + 1)) - math.pow(2, len(typeDict))
    diff -= td[1]
    if len(sorted_tdList) > 0:
        diff += sorted_tdList[0][1]
        sorted_tdList.pop(0)
    if diff > 0:
        ans += diff
    else:
        break

print(int(ans))

Submission status: Runtime Error

Solution code:
#ABC116D
import copy
N,K=map(int,input().split())
TD=[]
for n in range(N):
	TD.append(list(map(int,input().split())))
memo=[[-1 for k in range(K+1)] for n in range(N)]
V=[0 for n in range(N+1)]
def DP(i,k,p,v):
	global memo,N
	if k==0:#finish
		return p+v[0]**2
	elif N-i<k:#can not take K sushi
		if i<N:
			memo[i][k]=-2
		return -2
	elif memo[i][k]==-1:
		if v[TD[i][0]]==0:#unused
			vv=copy.deepcopy(v)
			vv[0]+=1
			vv[TD[i][0]]=1
			r=DP(i+1,k-1,p+TD[i][1],vv)
		else:#used
			r=DP(i+1,k-1,p+TD[i][1],v)
		r=max(r,DP(i+1,k,p,v))
		memo[i][k]=r
	else:
		r=memo[i][k]
	return r
print(DP(0,K,0,V))
#print(memo)

Submission status: Runtime Error

Solution code:
#ABC116D
import copy
N,K=map(int,input().split())
TD=[]
for n in range(N):
	TD.append(list(map(int,input().split())))
memo=[[-1 for k in range(K+1)] for n in range(N)]
V=[0 for n in range(N+1)]
def DP(i,k,p,v):
	global memo,N
	if k==0:#finish
		r=p+v[0]**2
	elif N-i<k:#can not take K sushi
		r=-2
	elif memo[i][k]==-1:
		if v[TD[i][0]]==0:#unused
			vv=copy.deepcopy(v)
			vv[0]+=1
			vv[TD[i][0]]=1
			r=DP(i+1,k-1,p+TD[i][1],vv)
		else:#used
			r=DP(i+1,k-1,p+TD[i][1],v)
		r=max(r,DP(i+1,k,p,v))
		memo[i][k]=r
	else:
		r=memo[i][k]
	return r

print(DP(0,K,0,V))

Submission status: Runtime Error

Solution code:
N,K = (int(x) for x in input().split())
td_arr = []
for _ in range(N):
    td = tuple(int(x) for x in input().split())
    td_arr.append(td)

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

n_dm_set = set()
small_arr = []
d_dm = 0
for t,d in td_arr[:K]:
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

candidate_dict = {}
candidate_dict[len(n_dm_set)] = d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
for t,d in td_arr[K:]:
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    candidate_dict[len(n_x_set)] = d_x

ans = 0
for k,v in candidate_dict.items():
    ans = max(ans, k*k+v)

print(ans)

Submission status: Runtime Error

Solution code:
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)
ans1=delicious+len(kind)**2
ans2=ans1
for t,d in TD[K:]:
    if not stack:break
    if not t in kind:
        ans2+=d-stack.pop()+2*len(kind)+1
        kind.add(t)
        ans2=max(ans1,ans2)
print(ans2)

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict
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)
sushi_types = set([])
sushi_tops = []
sushi_remains = []
for t, d in td:
    if not t in sushi_types:
        sushi_types.add(t)
        sushi_tops.append((t, d))
    else:
        sushi_remains.append((t, d))

n_types = len(sushi_types)
ans = sum([d for _, d in sushi_tops][:k]) + k**2
answers = [ans]
eat_types = set([t for t, _ in sushi_tops][:k])
i = 0
for t, d in sushi_tops[::-1]:
    eat_types.remove(t)
    while i < len(sushi_remains):
        t_r, d_r = sushi_remains[i]
        if t_r not in eat_types:
            i += 1
        else:
            ans = ans - d + d_r - (2*len(eat_types)+1)
            answers.append(ans)
            break
    # print(ans, (t, d), len(eat_types))
print(max(answers))

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split(' '))
TD = [[int(v) for v in input().split(' ')] for _ in range(N)]

dp = np.zeros((K+1, N+1), dtype=float)
nt = [['']*(N+1) for _ in range(K+1)]
for i in range(1, K+1):
    for j in range(1, N+1):
        
        if str(TD[j - 1][0]) in list(nt[i-1][j-1]):
            t_dp = dp[i - 1, j - 1] + TD[j - 1][1]
        else:
            v = len(nt[i - 1][j - 1])
            t_dp = dp[i - 1, j - 1] + TD[j - 1][1] - v**2 + (v+1)**2

        if dp[i, j-1] >= t_dp:
            dp[i, j] = dp[i, j-1]
            nt[i][j] = nt[i][j-1]
        else:
            dp[i, j] = t_dp
            if str(TD[j-1][0]) not in list(nt[i-1][j - 1]):
                nt[i][j] = nt[i-1][j - 1] + str(TD[j-1][0])
            else:
                nt[i][j] = nt[i - 1][j - 1]

print(int(dp[K, N]))

Submission status: Runtime Error

Solution code:
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 == N:
      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 == N:
    break


print(Ans)

Submission status: Runtime Error

Solution code:
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:
                types.add(t)
                tmp += d
                tmp -= stack.pop()
        ans = max(ans, tmp + len(types)**2)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# python template for atcoder1
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, v in reversed(selected):
    if vari[i] > 2:
        vari[i] -= 1
        can_del.append(v)

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

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

Submission status: Runtime Error

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

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

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

#-----------------------------------------
best_list=[]
best_list_neta=[]
not_best_list=[]

for i in li:
    if i[0] in best_list_neta:
        not_best_list.append(i[1])
    else:
        best_list.append(i[1])
        best_list_neta.append(i[0])


s2=min(len(best_list_neta),k)
s1=find_num_neta(list(range(k)),li)


score=-1
oishisa=[0 for i in range(n)]
oishisa[s1]=sum([li[p][1] for p in range(k)])

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

    if score<new_score:
        score=new_score
        
    
print(score)

Submission status: Runtime Error

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

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

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



#-----------------------------------------
best_list=[]
not_best_list=li.copy()

for i in li:
    if i[0] not in [best_list[p][0] for p in range(len(best_list))]:
        best_list.append(i)
        
for i in best_list:
    not_best_list.remove(i)

#-----------------------------------------
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)

oishisa=[0 for i in range(n)]
oishisa[s1]=sum([li[i][1] for i in range(k) ])
score=oishisa[s1]+s1**2

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

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while len(keseru)>0 and i<=k and right>=0 and left<=n-1 :
    while left<=n-1 and netalist[S[left][0]]!=0 :
        left+=1
    if left==n :
        break
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while len(keseru)>0 and i<=k and right>=0 and left<=n-1 :
    while left<=n-1 and netalist[S[left][0]]!=0 :
        left+=1
    if left==n-1 :
        break
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while len(keseru)>0 and i<=k and right>=0 and left<=n-1 :
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while i<=k and right>=0 and left<=n-1 :
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

netano_min=min(S[j][0] for j in range(n))
for i in range(n):
    S[i][0]-=netano_min-1

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

netano_min=min(S[j][0] for j in range(n))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while i<=k and right>=0 :
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]>=1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)
#print(netalist)

right=len(keseru)-1
left=k
i=neta_s+1
while i<=k and right>=0 :
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1
    i+=1

#print(F)
for j in range(neta_s,i+1-1) :
    F[j]+=j**2

print(max(F))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
S=[] #[ネタ種類、おいしさ]のリスト
for i in range(n):
    S.append(list(map(int,input().split())))
S.sort(reverse=1,key=lambda x:x[1])

neta=max(S[j][0] for j in range(n)) #ネタの種類数

F=[0 for i in range(neta+1)] #ネタi種のときの美味しさの和の最大値のリスト

ma=sum(S[i][1] for i in range(k))

neta_s=len(set([S[i][0] for i in range(k)]))

F[neta_s]=ma

#print(S)
#print(F)
#print(ma)

netalist=[0 for i in range(n)] #i種類目のネタを使った個数
keseru=[] #ネタに重複がある寿司のリスト(消してもいい寿司)
for i in range(k):
    if netalist[S[i][0]]==1 :
        keseru.append(S[i])
        
    netalist[S[i][0]]+=1

#print(keseru)

right=len(keseru)-1
left=k
for i in range(neta_s+1,k+1):
    while netalist[S[left][0]]!=0 :
        left+=1
    netalist[S[left][0]]+=1
    F[i]=F[i-1]+S[left][1]-keseru[right][1]
    right-=1
    left+=1

#print(F)
for i in range(neta_s,k+1) :
    F[i]+=i**2

print(max(F))