Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

from sys import stdin
from numpy import sum

input = stdin.readline

N, K = [int(n) for n in input().split()]
INPUT = [[None for i in range(2)] for j in range(N)]
List1, List2 = [], []
kind1 = []

for i in range(N):
    INPUT[i][0], INPUT[i][1] = [int(m) for m in input().split()]

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

for i in range(N):
    if INPUT[i][0] not in kind1:
            List1.append([INPUT[i][1], 1])
            kind1.append(INPUT[i][0])
    else: List1.append([INPUT[i][1], 0])

List2 = List1[K:]
if List2 != []:
    List2.sort(key =lambda x : (x[1],x[0]))
    del List1[K:]
    lenList2 = len(List2)
else: lenList2 = 0

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

sum = sum(List1, axis = 0)

Score = sum[0] + sum[1]**2
Test = Score
kindnumber = sum[1]

for i in range(lenList2):
    if List2[-1][1] == 0 or List1[-1][1] == 1:
        break
    Test = Test - List1.pop()[0] + List2.pop()[0] + 2 * kindnumber + 1
    kindnumber = kindnumber + 1
    if Test >= Score:
        Score = Test

print(int(Score))


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Runtime Error):
#ABC116D-VariousSushi.py

from sys import stdin
from numpy import sum

input = stdin.readline

N, K = [int(n) for n in input().split()]
INPUT = [[None for i in range(2)] for j in range(N)]
List1, List2 = [], []
kind1 = []
flag1 = 0

for i in range(N):
    INPUT[i][0], INPUT[i][1] = [int(m) for m in input().split()]

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

for i in range(N):
    if INPUT[i][0] not in kind1:
            List1.append([INPUT[i][1], 1])
            kind1.append(INPUT[i][0])
    else: List1.append([INPUT[i][1], 0])

List2 = List1[K:]
if List2 != []:
    List2.sort(key =lambda x : (x[1],x[0]))
    del List1[K:]
    lenList2 = len(List2)
else: lenList2 = 0

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

sum = sum(List1, axis = 0)

Score = sum[0] + sum[1]**2
Test = Score
kindnumber = sum[1]

for i in range(lenList2):
    if List2[-1][1] == 0 or List1[-1] == 1:
        break
    Test = Test - List1.pop()[0] + List2.pop()[0] + 2 * kindnumber + 1
    kindnumber = kindnumber + 1
    if Test >= Score:
        Score = Test
    i = i - 1

print(int(Score))


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Runtime Error):
#ABC116D-VariousSushi.py

from sys import stdin
from numpy import sum

input = stdin.readline

N, K = [int(n) for n in input().split()]
INPUT = [[None for i in range(2)] for j in range(N)]
List1, List2 = [], []
kind1 = []
flag1 = 0

for i in range(N):
    INPUT[i][0], INPUT[i][1] = [int(m) for m in input().split()]

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

for i in range(N):
    if INPUT[i][0] not in kind1:
            List1.append([INPUT[i][1], 1])
            kind1.append(INPUT[i][0])
    else: List1.append([INPUT[i][1], 0])

List2 = List1[K:]
List2.sort(key =lambda x : (x[1],x[0]))
del List1[K:]
List1 = sorted(List1, key = lambda x : (x[1], x[0]), reverse=True)

sum = sum(List1, axis = 0)

Score = sum[0] + sum[1]**2
Test = Score
lenList2 = len(List2)
kindnumber = sum[1]

for i in range(lenList2):
    if List2[-1][1] == 0 or List1[-1] == 1:
        break
    Test = Test - List1.pop()[0] + List2.pop()[0] + 2 * kindnumber + 1
    kindnumber = kindnumber + 1
    if Test >= Score:
        Score = Test
    i = i - 1

print(int(Score))


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Runtime Error):
#ABC116D-VariousSushi.py

import sys
import numpy as np

input = sys.stdin.readline

N, K = [int(n) for n in input().split()]
INPUT = [[None for i in range(2)] for j in range(N)]
List1, List2 = [], []
kind1, kind2 = [], []

for i in range(N):
    INPUT[i][0], INPUT[i][1] = [int(m) for m in input().split()]

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

for i in range(N):
    if INPUT[i][0] not in kind1:
        if len(List1) < K:
            List1.append(INPUT[i][1])
            kind1.append(INPUT[i][0])
    elif INPUT[i][0] not in kind2:
        List2.append(INPUT[i][1])
        kind2.append(INPUT[i][0])

List2.sort()

kindnumber = len(kind1)
k = len(List2)-(K-kindnumber)

Score = np.sum(List1) + np.sum(List2[k:]) + kindnumber ** 2
del List2[k:]
Test = Score

for i in range(kindnumber):
    Test = Test - List1.pop() + List2.pop() - 2 * kindnumber + 1
    kindnumber = kindnumber - 1
    if Test >= Score:
        Score = Test
    if List2 == []:
        break

print(int(Score))


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Runtime Error):
#ABC116D-VariousSushi.py

import sys
import numpy as np
from operator import itemgetter

input = sys.stdin.readline

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
List1, List2 = [], []
Score= 0
kind = []

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    if INPUT2[0] not in kind and len(List1) <= K:
        List1.append(INPUT2[1])
        kind.append(INPUT2[0])
    elif INPUT2[0] in kind:
        List2.append(INPUT2[1])

List1.sort(reverse=True)
List2.sort()

kindnumber = len(List1)
k = len(List2)-(K-kindnumber)

Score = np.sum(List1) + np.sum(List2[k:]) + kindnumber ** 2
del List2[k:]
Test = Score

for i in range(kindnumber):
    Test = Test - List1.pop() + List2.pop() - 2 * kindnumber + 1
    kindnumber = kindnumber - 1
    if Test >= Score:
        Score = Test
    if List2 == []:
        break

print(int(Score))


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

import sys
import numpy as np
from operator import itemgetter

input = sys.stdin.readline

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = [[None] * N for _ in range(N)]
Score= 0
kind = [None] * K
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters[i] = [INPUT2[0], INPUT2[1]]

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

def SearchNew(List, kind, I):
    newkind = -1
    kindset = kind[:]
    oldkindnumber = len(set(kindset))
    newkindnumber = 0
    for i in range(len(List)-I):
        kindset.append(List[I+i][0])
        newkindnumber = len(set(kindset))
        if oldkindnumber != newkindnumber:
            newkind = I+i
            break
    return newkind

def SearchDouble(List, kind, J):
    result = -1
    testkind = kind[:]
    oldkindnumber = len(set(testkind))
    testkindPop = testkind.pop
    for i in range(J):
        testkindPop(J-1-i)
        newkindnumber = len(set(testkind))
        if oldkindnumber == newkindnumber:
            result = J-1-i
            break
        oldkindnumber = newkindnumber
    return result

for i in range(K):
    kind[i] = Parameters[i][0]
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2

Test1, Test2 = 0, Score

I, J = K, K

for t in range(N):
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, kind, I)
    j = SearchDouble(Parameters, kind, J)
    if i != -1 and j != -1:
        kindnumber += 1
        I, J = i, j
        kind[j] = Parameters[i][0]
        Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

import numpy as np

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = [[None for col in range(2)] for row in range(N)]
Score= 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters[i] = [INPUT2[0], INPUT2[1]]

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

def SearchNew(List, kind, I):
    newkind = -1
    kindset = kind[:]
    oldkindnumber = len(set(kindset))
    newkindnumber = 0
    for i in range(len(List)-I):
        kindset.append(List[I+i][0])
        newkindnumber = len(set(kindset))
        if oldkindnumber != newkindnumber:
            newkind = I+i
            break
    return newkind

def SearchDouble(List, kind, J):
    result = -1
    testkind = kind[:]
    oldkindnumber = len(set(testkind))
    testkindPop = testkind.pop
    for i in range(J):
        testkindPop(J-1-i)
        newkindnumber = len(set(testkind))
        if oldkindnumber == newkindnumber:
            result = J-1-i
            break
        oldkindnumber = newkindnumber
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2

Test1, Test2 = 0, Score

I, J = K, K

for t in Parameters:
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, kind, I)
    j = SearchDouble(Parameters, kind, J)
    if i != -1 and j != -1:
        kindnumber += 1
        I, J = i, j
        kind[j] = Parameters[i][0]
        Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

import numpy as np
import bisect

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = [[None for col in range(2)] for row in range(N)]
Score= 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters[i] = [INPUT2[0], INPUT2[1]]

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

def SearchNew(List, K, kind):
    newkind = -1
    kindset = kind[:]
    oldkindnumber = 0
    newkindnumber = 0
    for i in range(len(List)-K):
        oldkindnumber = len(set(kindset))
        kindset.append(List[K+i][0])
        newkindnumber = len(set(kindset))
        if oldkindnumber != newkindnumber:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    testkind = kind[:]
    oldkindnumber = len(set(testkind))
    testkindPop = testkind.pop
    for i in range(K):
        testkindPop(K-1-i)
        newkindnumber = len(set(testkind))
        if oldkindnumber == newkindnumber:
            result = K-1-i
            break
        oldkindnumber = newkindnumber
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2
kind.clear()

Test1, Test2 = 0, Score

for t in Parameters:
    for i in range(K):
        kindAppend(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2
    kind.clear()

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

import numpy as np

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score= 0
kind = []
kindnumber = 0

ParametersAppend = Parameters.append
for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    ParametersAppend([INPUT2[0], INPUT2[1]])

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

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    testkind = kind[:]
    testkindPop = testkind.pop
    for i in range(K):
        testkindPop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2
kind.clear()

Test1, Test2 = 0, Score

for t in Parameters:
    for i in range(K):
        kindAppend(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2
    kind.clear()

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

ParametersAppend = Parameters.append
for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    ParametersAppend([INPUT2[0], INPUT2[1]])

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

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    testkind = kind[:]
    testkindPop = testkind.pop
    for i in range(K):
        testkindPop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)
kind.clear()

for t in Parameters:
    for i in range(K):
        kindAppend(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

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

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    for i in range(K):
        testkind = kind[:]
        testkind.pop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

for i in range(K):
    kind.append(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)
kind.clear()

for t in Parameters:
    for i in range(K):
        kind.append(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

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

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    for i in range(K):
        testkind = List[K-1-i][0]
        kind.pop(K-1-i)
        if testkind in kind:
            result = K-1-i
            break
    return result

for i in range(K):
    kind.append(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)

for t in Parameters:
    for i in range(K):
        kind.append(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
t, d = [], []


for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))


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

def SumScore(List, K):
    taste = 0
    kind = []
    for i in range(K):
        taste += List[i][1]
        kind.append(List[i][0])
    return taste + len(set(kind))**2

def SearchNew(List, K):
    kind = []
    newkind = -1
    for i in range(K):
        kind.append(List[i][0])
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K):
    result = -1
    leftkind = []
    for j in range(K):
        leftkind.append(List[j][0])
    for i in range(K):
        testkind = List[K-1-i][0]
        leftkind.pop(K-1-i)
        if testkind in leftkind:
            result = K-1-i
            break
    return result

Score = SumScore(Parameters, K)

for t in Parameters:
    i = SearchNew(Parameters, K)
    j = SearchDouble(Parameters, K)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    Test = SumScore(Parameters, K)
    if Score <= Test:
        Score = Test

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0


for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

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

def SumScore(List, K):
    taste = 0
    kind = []
    for i in range(K):
        taste += List[i][1]
        kind.append(List[i][0])
    return taste + len(set(kind))**2

def SearchNew(List, K):
    kind = []
    newkind = -1
    for i in range(K):
        kind.append(List[i][0])
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K):
    result = -1
    for i in range(K):
        leftkind = []
        for j in range(K):
            leftkind.append(List[j][0])
        testkind = List[K-1-i][0]
        leftkind.pop(K-1-i)
        if testkind in leftkind:
            result = K-1-i
            break
    return result

Score = SumScore(Parameters, K)

for t in Parameters:
    i = SearchNew(Parameters, K)
    j = SearchDouble(Parameters, K)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    Test = SumScore(Parameters, K)
    if Score <= Test:
        Score = Test

print(Score)


Fixed submission:
#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

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

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)