Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
from heapq import heapify, heappop, heappush
read = sys.stdin.read

N, K, *td = map(int, read().split())
dt = sorted(zip(td[1::2], td[::2]), reverse=True)

candidates = []
neta_group = Counter([j for i, j in dt[:K]])
variety = len(neta_group.keys())
points = sum([i for i, j in dt[:K]]) + variety ** 2
candidates.append(points)

if N == K:
    print(points)
    exit()

heap = [(-i, j) for i, j in dt[K:]]
heapify(heap)
satisfaction = dt[:K]
heapify(satisfaction)

while heap:
    taste, neta = heappop(heap)
    taste = -taste
    if not neta_group.get(neta):
        taste2, neta2 = heappop(satisfaction)
        if neta_group[neta2] == 1:
            heappush(heap, (-taste2, neta2))
        else:
            neta_group[neta2] -= 1
            neta_group[neta] = 1
            heappush(heap, (-taste, neta))
            points = points - taste2 + taste - variety ** 2 + (variety + 1) ** 2

            variety += 1
            candidates.append(points)

print(max(candidates))

Fixed submission:
import sys
from operator import itemgetter
read = sys.stdin.read

N, K, *td = map(int, read().split())
td = sorted(zip(*[iter(td)] * 2), key=itemgetter(1), reverse=True)

stack = []
taste = 0
neta_group = set()
for t, d in td[:K]:
    taste += d
    if t in neta_group:
        stack.append(d)
    else:
        neta_group.add(t)

variety = len(neta_group)
candidates = [taste + variety ** 2]

if N == K:
    print(candidates[0])
    exit()

rest = list(reversed(td[K::]))

while rest and stack:
    t1, d1 = rest.pop()
    if t1 not in neta_group:
        neta_group.add(t1)
        d2 = stack.pop()
        variety += 1
        taste = taste - d2 + d1

        candidates.append(taste + variety ** 2)

print(max(candidates))

Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
from heapq import heapify, heappop, heappush
read = sys.stdin.read

N, K, *td = map(int, read().split())
dt = sorted(zip(td[1::2], td[::2]), reverse=True)

candidates = []
neta_group = Counter([j for i, j in dt[:K]])
number = len(neta_group)
points = sum([i for i, j in dt[:K]]) + number ** 2
candidates.append(points)

heap = [(-i, j) for i, j in dt[K:]]
heapify(heap)
manzoku = dt[:K]
heapify(manzoku)

if N != K:
    while heap:
        oishisa, neta = heappop(heap)
        oishisa = -oishisa
        if not neta_group.get(neta):
            oishisa2, neta2 = heappop(manzoku)
            if neta_group[neta2] == 1:
                heappush(heap, (-oishisa2, neta2))
            else:
                neta_group[neta2] -= 1
                neta_group[neta] = 1
                heappush(heap, (-oishisa, neta))
                points = points - oishisa2 + oishisa - number ** 2 + (number + 1) ** 2

                number += 1
                candidates.append(points)

print(max(candidates))

Fixed submission:
import sys
from operator import itemgetter
read = sys.stdin.read

N, K, *td = map(int, read().split())
td = sorted(zip(*[iter(td)] * 2), key=itemgetter(1), reverse=True)

stack = []
taste = 0
neta_group = set()
for t, d in td[:K]:
    taste += d
    if t in neta_group:
        stack.append(d)
    else:
        neta_group.add(t)

variety = len(neta_group)
candidates = [taste + variety ** 2]

if N == K:
    print(candidates[0])
    exit()

rest = list(reversed(td[K::]))

while rest and stack:
    t1, d1 = rest.pop()
    if t1 not in neta_group:
        neta_group.add(t1)
        d2 = stack.pop()
        variety += 1
        taste = taste - d2 + d1

        candidates.append(taste + variety ** 2)

print(max(candidates))

Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
from heapq import heapify, heappop, heappush
read = sys.stdin.read

N, K, *td = map(int, read().split())
dt = sorted(zip(td[1::2], td[::2]), reverse=True)

candidates = []
neta_group = Counter([j for i, j in dt[:K]])
number = len(neta_group)
points = sum([i for i, j in dt[:K]]) + number ** 2
candidates.append(points)

heap = [(-i, j) for i, j in dt[K:]]
heapify(heap)
manzoku = dt[:K]
heapify(manzoku)

while heap:
    oishisa, neta = heappop(heap)
    oishisa = -oishisa
    if not neta_group.get(neta):
        oishisa2, neta2 = heappop(manzoku)
        if neta_group[neta2] == 1:
            heappush(heap, (-oishisa2, neta2))
        else:
            neta_group[neta2] -= 1
            neta_group[neta] = 1
            heappush(heap, (-oishisa, neta))
            points = points - oishisa2 + oishisa - number ** 2 + (number + 1) ** 2

            number += 1
            candidates.append(points)

print(max(candidates))

Fixed submission:
import sys
from operator import itemgetter
read = sys.stdin.read

N, K, *td = map(int, read().split())
td = sorted(zip(*[iter(td)] * 2), key=itemgetter(1), reverse=True)

stack = []
taste = 0
neta_group = set()
for t, d in td[:K]:
    taste += d
    if t in neta_group:
        stack.append(d)
    else:
        neta_group.add(t)

variety = len(neta_group)
candidates = [taste + variety ** 2]

if N == K:
    print(candidates[0])
    exit()

rest = list(reversed(td[K::]))

while rest and stack:
    t1, d1 = rest.pop()
    if t1 not in neta_group:
        neta_group.add(t1)
        d2 = stack.pop()
        variety += 1
        taste = taste - d2 + d1

        candidates.append(taste + variety ** 2)

print(max(candidates))

Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
from heapq import heapify, heappop, heappush
read = sys.stdin.read

N, K, *td = map(int, read().split())
dt = sorted(zip(td[1::2], td[::2]), reverse=True)

candidates = []
points = sum([i for i, j in dt[:K]]) + len(set([j for i, j in dt[:K]])) ** 2
neta_group = Counter([j for i, j in dt[:K]])
candidates.append(points)

heap = [(-i, j) for i, j in dt[K:]]
heapify(heap)
manzoku = dt[:K]
heapify(manzoku)

while heap:
    oishisa, neta = heappop(heap)
    oishisa = -oishisa
    if not neta_group.get(neta):
        oishisa2, neta2 = heappop(manzoku)
        if neta_group[neta2] == 1:
            heappush(heap, (-oishisa2, neta2))
        else:
            neta_group[neta2] -= 1
            neta_group[neta] = 1
            heappush(heap, (-oishisa, neta))
            points = points - oishisa2 + oishisa - (len(neta_group.keys()) - 1) ** 2 + len(neta_group.keys()) ** 2
            candidates.append(points)

print(max(candidates))

Fixed submission:
import sys
from operator import itemgetter
read = sys.stdin.read

N, K, *td = map(int, read().split())
td = sorted(zip(*[iter(td)] * 2), key=itemgetter(1), reverse=True)

stack = []
taste = 0
neta_group = set()
for t, d in td[:K]:
    taste += d
    if t in neta_group:
        stack.append(d)
    else:
        neta_group.add(t)

variety = len(neta_group)
candidates = [taste + variety ** 2]

if N == K:
    print(candidates[0])
    exit()

rest = list(reversed(td[K::]))

while rest and stack:
    t1, d1 = rest.pop()
    if t1 not in neta_group:
        neta_group.add(t1)
        d2 = stack.pop()
        variety += 1
        taste = taste - d2 + d1

        candidates.append(taste + variety ** 2)

print(max(candidates))