Buggy python submission (verdict: Runtime Error):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    type_count = [0] * 10000
    base_point = 0
    type_bonus = 0
    #  for idx, i in enumerate(TD[:K]):
    #      #  if not type_count_dict.get(i[0]):
    #      #      type_count_dict[i[0]] = 0
    #      #  if idx < K:
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          type_bonus += 1
    #      #  type_count_dict[i[0]] += 1
    #      type_count[i[0]] += 1
    #      base_point += i[1]
    #  #  print(type_count_dict)

    remaining_items = []
    for idx, i in enumerate(TD):
        if idx < K:
            if type_count[i[0]] == 0:
                type_bonus += 1
            type_count[i[0]] += 1
            base_point += i[1]
        else:
            if type_count[i[0]] == 0:
                remaining_items.append(i[1])
                type_count[i[0]] += 1

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  print('result', result, base_point, type_bonus)
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  #  remaining_items = PriorityQueue()
    #  done_types = []
    #  #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  #  print('remaining_items', remaining_items)

    if len(remaining_items) == 0:
        print(result)
        return
    ridx = 0
    for s in S[::-1]:
        if len(remaining_items) < ridx + 1:
            break
        #  if remaining_items.empty():
        #      break
        #  if type_count_dict[s[0]] >= 2:
        if type_count[s[0]] >= 2:
            # print('s', s)
            #  type_count_dict[s[0]] -= 1
            type_count[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    type_count = [0] * 10000
    base_point = 0
    type_bonus = 0
    #  for idx, i in enumerate(TD[:K]):
    #      #  if not type_count_dict.get(i[0]):
    #      #      type_count_dict[i[0]] = 0
    #      #  if idx < K:
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          type_bonus += 1
    #      #  type_count_dict[i[0]] += 1
    #      type_count[i[0]] += 1
    #      base_point += i[1]
    #  #  print(type_count_dict)

    remaining_items = []
    for idx, i in enumerate(TD):
        if idx < K:
            if type_count[i[0]] == 0:
                type_bonus += 1
            type_count[i[0]] += 1
            base_point += i[1]
        else:
            if type_count[i[0]] == 0:
                remaining_items.append(i[1])
                type_count[i[0]] += 1

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  print('result', result, base_point, type_bonus)
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  #  remaining_items = PriorityQueue()
    #  done_types = []
    #  #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  #  print('remaining_items', remaining_items)

    if len(remaining_items) == 0:
        print(result)
        return
    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        #  if remaining_items.empty():
        #      break
        #  if type_count_dict[s[0]] >= 2:
        if type_count[s[0]] >= 2:
            # print('s', s)
            #  type_count_dict[s[0]] -= 1
            type_count[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    type_count = [0] * 10000
    base_point = 0
    type_bonus = 0
    #  for idx, i in enumerate(TD[:K]):
    #      #  if not type_count_dict.get(i[0]):
    #      #      type_count_dict[i[0]] = 0
    #      #  if idx < K:
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          type_bonus += 1
    #      #  type_count_dict[i[0]] += 1
    #      type_count[i[0]] += 1
    #      base_point += i[1]
    #  #  print(type_count_dict)

    remaining_items = []
    for idx, i in enumerate(TD):
        if idx < K:
            if type_count[i[0]] == 0:
                type_bonus += 1
            type_count[i[0]] += 1
            base_point += i[1]
        else:
            if type_count[i[0]] == 0:
                remaining_items.append(i[1])
                type_count[i[0]] += 1

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  print('result', result, base_point, type_bonus)
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  #  remaining_items = PriorityQueue()
    #  done_types = []
    #  #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      #  if type_count_dict[i[0]] == 0:
    #      if type_count[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        #  if type_count_dict[s[0]] >= 2:
        if type_count[s[0]] >= 2:
            # print('s', s)
            #  type_count_dict[s[0]] -= 1
            type_count[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    type_count = [0] * 10000
    base_point = 0
    type_bonus = 0
    for idx, i in enumerate(TD):
        #  if not type_count_dict.get(i[0]):
        #      type_count_dict[i[0]] = 0
        if idx < K:
            #  if type_count_dict[i[0]] == 0:
            if type_count[i[0]] == 0:
                type_bonus += 1
            #  type_count_dict[i[0]] += 1
            type_count[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    #  remaining_items = PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        #  if type_count_dict[i[0]] == 0:
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            #  remaining_items.put((-i[1], i[1]))
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        #  if type_count_dict[s[0]] >= 2:
        if type_count[s[0]] >= 2:
            # print('s', s)
            #  type_count_dict[s[0]] -= 1
            type_count[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    #  remaining_items = PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            #  remaining_items.put((-i[1], i[1]))
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    remaining_items = PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            #  remaining_items.append(i[1])
            remaining_items.put((-i[1], i[1]))
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        #  if len(remaining_items) < ridx + 1:
        #      break
        #  if len(remaining_items) == 0:
        #      break
        if remaining_items.empty():
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            #  base_point += remaining_items[ridx] - s[1]
            base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            #  ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    remaining_items = PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            #  remaining_items.append(i[1])
            remaining_items.put((-i[1], i[1]))
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        #  if len(remaining_items) < ridx + 1:
        #      break
        #  if len(remaining_items) == 0:
        #      break
        if remaining_items.empty():
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            #  base_point += remaining_items[ridx] - s[1]
            base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            #  ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            type_count_dict[i[0]] += 1
            base_point += i[1]
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    base_point = 0
    for i in S:
        type_count_dict[i[0]] += 1
        base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    base_point = 0
    for i in S:
        type_count_dict[i[0]] += 1
        base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


if __name__ == '__main__':
    main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np
from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    remaining_items = PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            #  remaining_items.append(i[1])
            remaining_items.put((-i[1], i[1]))
            done_types.append(i[0])

    for idx, s in enumerate(S[::-1]):
        if remaining_items.empty():
            break
        if type_count_dict[s[0]] >= 2:
            type_count_dict[s[0]] -= 1
            base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))
   

main()
		

Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))
   

main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = queue.PriorityQueue()
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            #  remaining_items.append(i[1])
            remaining_items.put(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            type_bonus += 1
            ridx += 1
            results.append(type_bonus**2 + base_point)

    print(max(results))
   

main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[0] - s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            #  print(type_bonus)
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    for i in TD:
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    for i in S:
        type_count_dict[i[0]] += 1

    #  print('type_count', type_count_dict)
    base_point = sum(i[1] for i in S)
    type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    #  print('type_count_dict', type_count_dict)
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count_dict[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[0] - s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            #  print(type_bonus)
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    # print(TD)
    # 種類のカウントをもつ
    #  print(max(TD, key=lambda x:x[1]))
    type_count = [0 for i in range(max(TD, key=lambda x:x[1])[1] + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = sum(i[1] for i in S)
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    results = [result]
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point += remaining_items[0] - s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    # print(TD)
    # 種類のカウントをもつ
    #  print(max(TD, key=lambda x:x[1]))
    type_count = [0 for i in range(max(TD, key=lambda x:x[1])[1] + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = sum(i[1] for i in S)
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    results = [result]
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point += remaining_items[0] - s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    # print(TD)
    # 種類のカウントをもつ
    #  print(max(TD, key=lambda x:x[1]))
    type_count = [0 for i in range(max(TD, key=lambda x:x[1])[1] + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = sum(i[1] for i in S)
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    results = [result]
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point -= s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            base_point += remaining_items[0]
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
#  import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    # print(TD)
    # 種類のカウントをもつ
    #  print(max(TD, key=lambda x:x[1]))
    type_count = [0 for i in range(max(TD, key=lambda x:x[1])[1] + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = sum(i[1] for i in S)
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    results = [result]
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point -= s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            base_point += remaining_items[0]
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    TD = np.array(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    # print(TD)
    # 種類のカウントをもつ
    type_count = [0 for i in range(max(TD[:, 0]) + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = np.sum(S[:, 1])
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    results = [result]
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point -= s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            base_point += remaining_items[0]
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            results.append(type_bonus**2 + base_point)

    print(max(results))
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    TD = np.array(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    # print(TD)
    # 種類のカウントをもつ
    type_count = [0 for i in range(max(TD[:, 0]) + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = np.sum(S[:, 1])
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point -= s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            base_point += remaining_items[0]
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            del remaining_items[0]
            result = max(result, type_bonus**2 + base_point)

    print(result)
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    TD = np.array(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    # print(TD)
    # 種類のカウントをもつ
    type_count = [0 for i in range(max(TD[:, 0]) + 1)]

    S = TD[:K]
    # print('S', S)
    for i in S:
        type_count[i[0]] += 1

    # print('type_count', type_count)
    base_point = np.sum(S[:, 1])
    type_bonus = len([i for i in type_count if i != 0])
    result = base_point + type_bonus**2
    # print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    remaining_items = []
    done_types = []
    for i in TD[K:]:
        if i[0] in done_types:
            continue
        if type_count[i[0]] == 0:
            remaining_items.append(i[1])
            done_types.append(i[0])
    # print('remaining_items', remaining_items)

    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) == 0:
            break
        if type_count[s[0]] >= 2:
            # print('s', s)
            type_count[s[0]] -= 1
            base_point -= s[1]
            #  S[len(S) - 1 - idx] = TD[remaining_items[0]]
            type_bonus += 1
            # print('base_point1', base_point)
            base_point += remaining_items[0]
            # print('base_point2', base_point)
            # print('type_bonus', type_bonus)
            #  del remaining_items[0]
            result = max(result, type_bonus**2 + base_point)

    print(result)
    
main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np


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


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

def main():
    # 問題をdfs的手法で解いてみる
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    TD = np.array(TD)
    # print(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    neta_type_list = set([i[0] for i in TD])

    # print("neta_type, TD\n", neta_type_list, TD)
    result = 0
    for k in range(1, K+1):
        if k > len(neta_type_list):
            break
        # 1種類の場合のみ分けて考える
        if k == 1:
            result = sum([i[1] for i in TD[:K]]) + 1
            continue
        # k種類選ぶ場合を考える
        # タイプごとのカウントを保持する
        # print('\n=====k種類選ぶ場合', k, k*k)
        result = max(result, find_max_combi_value(neta_type_list, TD, k, K) + k*k)

    print(result)


def find_max_combi_value(neta_type_list, TD, k, K):
        c = 0
        type_count = [[i, 0] for i in neta_type_list]
        result = 0
        # そもそも組み合わせが作れない場合
        type_length_list = np.zeros(max([i[0] for i in TD]) + 1)
        for i in TD:
            type_length_list[i[0]] += 1
        # print(type_length_list)
        type_length_list = np.sort(type_length_list)[::-1]
        # print(type_length_list)
        if sum(type_length_list[:k]) < K:
            return 0

        while True:
            # print('\nc', c)
            # print('while type-count', type_count)
            # まず種類分確保しなくてはいけない
            # print('TD[c]\n', TD[c])
            old_type_count = copy.copy(type_count)
            # print('initial, 999909909', old_type_count, type_count)

            for idx, i in enumerate(type_count):
                try:
                    if i[0] == TD[c][0]:
                        type_count[idx][1] += 1
                except:
                    import pdb
                    pdb.set_trace()
            type_count = np.array(type_count)
            type_count = type_count[np.argsort(type_count[:, 1])[::-1]]
            result += TD[c][1]
            # i個最大のものをとって、Kに達していたら終了
            if type_count[0][1] > K - k + 1:
                # print('111111', old_type_count)
                type_count = copy.copy(old_type_count)
                result -= TD[c][1]
                # print('result0', result)
                c += 1
                continue

            # ちょうどK個選んだ場合
            # print('選んだ個数合計', sum([i[1] for i in type_count[:k]]))
            if sum([i[1] for i in type_count[:k]]) == K:
                # 0がある場合はだめ
                if any([i[1] == 0 for i in type_count[:k]]):
                    # print('======', c, type_count)
                    result -= TD[c][1]
                    type_count = copy.copy(old_type_count)
                    # print('result1', result)
                    c += 1
                    continue
                # print('end type-count\n', type_count)
                return result
            if c == len(TD)-1:
                return 0
            # print('type_count ending', type_count)
            # print('result2', result)
            old_type_count = copy.copy(type_count)
            c += 1


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np


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


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

def main():
    # 問題をdfs的手法で解いてみる
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    TD = np.array(TD)
    # print(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    neta_type_list = set([i[0] for i in TD])

    # print("neta_type, TD\n", neta_type_list, TD)
    result = 0
    for k in range(1, K+1):
        # 1種類の場合のみ分けて考える
        if k == 1:
            result = TD[0][1] + 1
            continue
        # k種類選ぶ場合を考える
        # タイプごとのカウントを保持する
        # print('\n=====k種類選ぶ場合', k, k*k)
        result = max(result, find_max_combi_value(neta_type_list, TD, k, K) + k*k)

    print(result)


def find_max_combi_value(neta_type_list, TD, k, K):
        c = 0
        type_count = [[i, 0] for i in neta_type_list]
        result = 0
        # そもそも組み合わせが作れない場合
        type_length_list = np.zeros(max([i[0] for i in TD]) + 1)
        for i in TD:
            type_length_list[i[0]] += 1
        # print(type_length_list)
        type_length_list = np.sort(type_length_list)[::-1]
        # print(type_length_list)
        if sum(type_length_list[:k]) < K:
            return 0

        while True:
            # print('\nc', c)
            # print('while type-count', type_count)
            # まず種類分確保しなくてはいけない
            # print('TD[c]\n', TD[c])
            old_type_count = copy.copy(type_count)
            # print('initial, 999909909', old_type_count, type_count)

            for idx, i in enumerate(type_count):
                try:
                    if i[0] == TD[c][0]:
                        type_count[idx][1] += 1
                except:
                    import pdb
                    pdb.set_trace()
            type_count = np.array(type_count)
            type_count = type_count[np.argsort(type_count[:, 1])[::-1]]
            result += TD[c][1]
            # i個最大のものをとって、Kに達していたら終了
            if type_count[0][1] > K - k + 1:
                # print('111111', old_type_count)
                type_count = copy.copy(old_type_count)
                result -= TD[c][1]
                # print('result0', result)
                c += 1
                continue

            # ちょうどK個選んだ場合
            # print('選んだ個数合計', sum([i[1] for i in type_count[:k]]))
            if sum([i[1] for i in type_count[:k]]) == K:
                # 0がある場合はだめ
                if any([i[1] == 0 for i in type_count[:k]]):
                    # print('======', c, type_count)
                    result -= TD[c][1]
                    type_count = copy.copy(old_type_count)
                    # print('result1', result)
                    c += 1
                    continue
                # print('end type-count\n', type_count)
                return result
            if c == len(TD)-1:
                return 0
            # print('type_count ending', type_count)
            # print('result2', result)
            old_type_count = copy.copy(type_count)
            c += 1


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np


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


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

def main():
    # 問題をdfs的手法で解いてみる
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    TD = np.array(TD)
    # print(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    neta_type_list = set([i[0] for i in TD])

    # print("neta_type, TD\n", neta_type_list, TD)
    result = 0
    for k in range(1, K+1):
        # 1種類の場合のみ分けて考える
        if k == 1:
            result = TD[0][1] + 1
            continue
        # k種類選ぶ場合を考える
        # タイプごとのカウントを保持する
        # print('\n=====k種類選ぶ場合', k, k*k)
        result = max(result, find_max_combi_value(neta_type_list, TD, k, K) + k*k)

    print(result)


def find_max_combi_value(neta_type_list, TD, k, K):
        c = 0
        type_count = [[i, 0] for i in neta_type_list]
        result = 0
        # そもそも組み合わせが作れない場合
        type_length_list = np.zeros(max([i[0] for i in TD]) + 1)
        for i in TD:
            type_length_list[i[0]] += 1
        # print(type_length_list)
        type_length_list = np.sort(type_length_list)[::-1]
        # print(type_length_list)
        if sum(type_length_list[:k]) < K:
            return 0

        while True:
            # print('\nc', c)
            # print('while type-count', type_count)
            # まず種類分確保しなくてはいけない
            # print('TD[c]\n', TD[c])
            old_type_count = copy.copy(type_count)
            # print('initial, 999909909', old_type_count, type_count)

            for idx, i in enumerate(type_count):
                if i[0] == TD[c][0]:
                    type_count[idx][1] += 1
            type_count = np.array(type_count)
            type_count = type_count[np.argsort(type_count[:, 1])[::-1]]
            result += TD[c][1]
            # i個最大のものをとって、Kに達していたら終了
            if type_count[0][1] > K - k + 1:
                # print('111111', old_type_count)
                type_count = copy.copy(old_type_count)
                result -= TD[c][1]
                # print('result0', result)
                c += 1
                continue

            # ちょうどK個選んだ場合
            # print('選んだ個数合計', sum([i[1] for i in type_count[:k]]))
            if sum([i[1] for i in type_count[:k]]) == K:
                # 0がある場合はだめ
                if any([i[1] == 0 for i in type_count[:k]]):
                    # print('======', c, type_count)
                    result -= TD[c][1]
                    type_count = copy.copy(old_type_count)
                    # print('result1', result)
                    c += 1
                    continue
                # print('end type-count\n', type_count)
                return result
            if c == len(TD-1):
                return 0
            # print('type_count ending', type_count)
            # print('result2', result)
            old_type_count = copy.copy(type_count)
            c += 1


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np


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


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

def main():
    # 問題をdfs的手法で解いてみる
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    TD = np.array(TD)
    # print(TD)
    TD = TD[np.argsort(TD[:, 1])[::-1]]

    neta_type_list = set([i[0] for i in TD])

    # print("neta_type, TD\n", neta_type_list, TD)
    result = 0
    if K == 0:
        print(0)
        return

    for k in range(1, K+1):
        # 1種類の場合のみ分けて考える
        if k == 1:
            result = max([t[1] for t in TD])
            continue
        # k種類選ぶ場合を考える
        # タイプごとのカウントを保持する
        # print('\n=====k種類選ぶ場合', k, k*k)
        result = max(result, find_max_combi_value(neta_type_list, TD, k, K) + k*k)

    print(result)


def find_max_combi_value(neta_type_list, TD, k, K):
        c = 0
        type_count = [[i, 0] for i in neta_type_list]
        result = 0
        # そもそも組み合わせが作れない場合
        type_length_list = np.zeros(max([i[0] for i in TD]) + 1)
        for i in TD:
            type_length_list[i[0]] += 1
        # print(type_length_list)
        type_length_list = np.sort(type_length_list)[::-1]
        # print(type_length_list)
        if sum(type_length_list[:k]) < K:
            return 0

        while True:
            # print('\nc', c)
            # print('while type-count', type_count)
            # まず種類分確保しなくてはいけない
            # print('TD[c]\n', TD[c])
            old_type_count = copy.copy(type_count)
            # print('initial, 999909909', old_type_count, type_count)

            for idx, i in enumerate(type_count):
                if i[0] == TD[c][0]:
                    type_count[idx][1] += 1
            type_count = np.array(type_count)
            type_count = type_count[np.argsort(type_count[:, 1])[::-1]]
            result += TD[c][1]
            # i個最大のものをとって、Kに達していたら終了
            if type_count[0][1] > K - k + 1:
                # print('111111', old_type_count)
                type_count = copy.copy(old_type_count)
                result -= TD[c][1]
                # print('result0', result)
                c += 1
                continue

            # ちょうどK個選んだ場合
            # print('選んだ個数合計', sum([i[1] for i in type_count[:k]]))
            if sum([i[1] for i in type_count[:k]]) == K:
                # 0がある場合はだめ
                if any([i[1] == 0 for i in type_count[:k]]):
                    # print('======', c, type_count)
                    result -= TD[c][1]
                    type_count = copy.copy(old_type_count)
                    # print('result1', result)
                    c += 1
                    continue
                # print('end type-count\n', type_count)
                return result
            if c == len(TD-1):
                return 0
            # print('type_count ending', type_count)
            # print('result2', result)
            old_type_count = copy.copy(type_count)
            c += 1


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
from operator import itemgetter


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


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

def main():
    # 種類最小から最大までそれぞれ計算する
    N, K = LI()
    T = []
    D = []
    TD = []
    for i in range(N):
        TD.append(LI())
    #  print(T, '\n', D)
    TD = sorted(TD, key=itemgetter(1), reverse=True)
    #  print('TD', TD)

    max_value_per_type = [[t, max([td[1] for td in TD if td[0] == t])]for t in set([i[0] for i in TD])]
    #  print('max_value_per_type', max_value_per_type)
    content_per_type = [[t, [i[1] for i in TD if i[0] == t]] for t in set(i[0] for i in TD)]
    #  print(content_per_type)
    max_idx_per_type = [i[1].index([mvpt[1] for mvpt in max_value_per_type if mvpt[0] == i[0]][0]) for i in content_per_type]
    #  print('max_idx_per_type', max_idx_per_type)
    for idx, i in enumerate(max_idx_per_type):
        del content_per_type[idx][1][i]
    #  remaining_values_per_type = [[c[0], [i[0] for i in content_per_type if ]] for c in content_per_type]
    #  print('各タイプから最大値を抜きました', content_per_type)
    results = [0]
    for i in range(1, K+1):
        #  print('\n---------\n',i,'回目')
        # iを種類数とみなす
        # 何を選んだかは関係ない
        
        # 種類の全組み合わせを求める
        #  print(i)
        if len(set([i[0] for i in TD])) < i:
            break 
        combinations = list(itertools.combinations(set([i[0] for i in TD]), i))
        #  print('combi', combinations)
        type_bonus = i * i
        for combination in combinations:
            #  print('\n')
            # 各組み合わせでの最大値を求める
            current_options = [i for i in TD if i[0] in combination]
            #  print('current_options: ', current_options)
            # そもそも数がKに満たない場合は作るのが不可能なため次のループへ
            if len(current_options) < K:
                continue

            max_values = [i[1] for i in max_value_per_type if i[0] in combination]
            current_options = [i[1] for i in content_per_type if i[0] in combination]
            current_options = list(itertools.chain.from_iterable(current_options))
            current_options.sort(reverse=True)
            #  print('最大値だけとった', base_point)
            #  print('残りの選択肢', current_options)
            results.append(sum(current_options[:K-i]) + sum(max_values) + type_bonus)

    #  print('\n======================\nresults', results)
    print(max(results))


main()


Fixed submission:
#  import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
#  import numpy as np
#  from queue import PriorityQueue

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


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


def main():
    N, K = LI()
    T = []
    D = []
    TD = []
    [TD.append(LI()) for i in range(N)]
    # sort desc
    #  TD = np.array(TD)
    #  TD = TD[np.argsort(TD[:, 1])[::-1]]
    TD = sorted(TD, key=lambda l:l[1], reverse=True)
    #  print(TD)

    #  print(TD)
    # 種類のカウントをもつ
    type_count_dict = {}
    base_point = 0
    type_bonus = 0
    remaining_items = []
    for idx, i in enumerate(TD):
        if not type_count_dict.get(i[0]):
            type_count_dict[i[0]] = 0
        if idx < K:
            if type_count_dict[i[0]] == 0:
                type_bonus += 1
            type_count_dict[i[0]] += 1
            base_point += i[1]
        else:
            if type_count_dict[i[0]] == 0:
                remaining_items.append(i[1])
                type_count_dict[i[0]] += 1

    #  print(type_count_dict)

    S = TD[:K]
    #  print('S', S)
    #  for i in S:
    #      type_count_dict[i[0]] += 1
    #      base_point += i[1]

    #  print('type_count', type_count_dict)
    #  base_point = sum(i[1] for i in S)
    #  type_bonus = len(set([i[0] for i in S]))
    result = base_point + type_bonus**2
    #  results = [result]
    #  print('base_point, type_bonus, result', base_point, type_bonus**2, result)

    #  remaining_items = []
    #  remaining_items = PriorityQueue()
    #  done_types = []
    #  print('type_count_dict', type_count_dict)
    #  for i in TD[K:]:
    #      if i[0] in done_types:
    #          continue
    #      if type_count_dict[i[0]] == 0:
    #          remaining_items.append(i[1])
    #          #  remaining_items.put((-i[1], i[1]))
    #          done_types.append(i[0])
    #  print('remaining_items', remaining_items)

    ridx = 0
    for idx, s in enumerate(S[::-1]):
        if len(remaining_items) < ridx + 1:
            break
        if len(remaining_items) == 0:
            break
        #  if remaining_items.empty():
        #      break
        if type_count_dict[s[0]] >= 2:
            # print('s', s)
            type_count_dict[s[0]] -= 1
            base_point += remaining_items[ridx] - s[1]
            #  base_point += remaining_items.get()[1] - s[1]
            type_bonus += 1
            ridx += 1
            #  results.append(type_bonus**2 + base_point)
            result = max(type_bonus**2 + base_point, result)

    #  print(max(results))
    print(result)


if __name__ == '__main__':
    main()