Problem p03148 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heapify,heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,k = LI()
    g = LIR(n)
    g.sort(key = lambda x:-x[1])
    f = [0 for i in range(n+1)]
    x = 0
    ans = 0
    c = []
    for i in range(k):
        ans += g[i][1]
        if not f[g[i][0]]:x+=1
        else:c.append(g[i][1])
        f[g[i][0]] += 1
    ans += x**2
    c.sort()
    c = deque(c)
    d = ans
    for i in range(k,n):
        if not c:
            break
        if f[g[i][0]]:continue
        d += g[i][1]-c.popleft()+2*x+1
        f[g[i][0]] = 1
        x += 1
        if d > ans:
            ans = d
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def LIR(n): return [LI() for i in range(n)]
mod = 1000000007

#A
"""
a,b,c = LI()
s = a+b+c
s /= 2
ans = (s*(s-a)*(s-b)*(s-c))**(1/2)
print(int(ans))
"""

#B
"""
s = int(input())
m = 1
lis = [True for i in range(1000001)]

while lis[s]:
    lis[s] = False
    if s % 2 == 1:
        s = 3*s+1
    else:
        s //= 2
    m += 1
print(m)
"""

#C
"""
n = II()
h = LI()
ans = 0
while sum(h) != 0:
    l = 0
    while h[l] == 0: l += 1
    r = l
    while r < n:
        if h[r] == 0: break
        h[r] -= 1
        r += 1
    ans += 1
print(ans)
"""

#D
n,k = LI()
lis = LIR(n)
lis.sort(key = lambda x:x[1])
lis = lis[::-1]
num = [False for i in range(n)]
count = [0 for i in range(n)]
for i in range(n):
    lis[i][0] -= 1
ans = 0
t = 0
l = []
for i in range(k):
    ans += lis[i][1]
    count[lis[i][0]] += 1
    if not num[lis[i][0]]:
        t += 1
    num[lis[i][0]] = True
for i in range(k):
    if count[i] != 1:
        l.append(lis[i])
l = l[::-1]

a = [0 for i in range(len(l))]
for i in range(len(l)):
    a[i] = l[i][1]
for i in range(len(l)-1):
    a[i+1] += a[i]
li = []

for i in range(n):
    if not num[lis[i][0]]:
        li.append(lis[i][1])
        num[lis[i][0]] = True
b = [0 for i in range(len(li))]
for i in range(len(li)):
    b[i] = li[i]
for i in range(len(li)-1):
    b[i+1] += b[i]
d = [[ans,t] for i in range(min(len(l),len(li))+1)]

for i in range(len(d)-1):
    d[i+1][0] += b[i] - a[i]
    d[i+1][1] = min(k,t+i+1)
ans = 0
for i in range(len(d)+1):
    ans = max(ans, d[i][0]+d[i][1]**2)
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def LIR(n): return [LI() for i in range(n)]
mod = 1000000007

#A
"""
a,b,c = LI()
s = a+b+c
s /= 2
ans = (s*(s-a)*(s-b)*(s-c))**(1/2)
print(int(ans))
"""

#B
"""
s = int(input())
m = 1
lis = [True for i in range(1000001)]

while lis[s]:
    lis[s] = False
    if s % 2 == 1:
        s = 3*s+1
    else:
        s //= 2
    m += 1
print(m)
"""

#C
"""
n = II()
h = LI()
ans = 0
while sum(h) != 0:
    l = 0
    while h[l] == 0: l += 1
    r = l
    while r < n:
        if h[r] == 0: break
        h[r] -= 1
        r += 1
    ans += 1
print(ans)
"""

#D
n,k = LI()
lis = LIR(n)
lis.sort(key = lambda x:x[1])
lis = lis[::-1]
num = [False for i in range(n)]
count = [0 for i in range(n)]
for i in range(n):
    lis[i][0] -= 1
ans = 0
t = 0
l = []
for i in range(k):
    ans += lis[i][1]
    count[lis[i][0]] += 1
    if not num[lis[i][0]]:
        t += 1
    num[lis[i][0]] = True
for i in range(k):
    if count[i] != 1:
        l.append(lis[i])
l = l[::-1]

a = [0 for i in range(len(l))]
for i in range(len(l)):
    a[i] = l[i][1]
for i in range(len(l)-1):
    a[i+1] += a[i]
li = []

for i in range(n):
    if not num[lis[i][0]]:
        li.append(lis[i][1])
        num[lis[i][0]] = True
b = [0 for i in range(len(li))]
for i in range(len(li)):
    b[i] = li[i]
for i in range(len(li)-1):
    b[i+1] += b[i]
d = [[ans,t] for i in range(min(len(l),len(li))+1)]

for i in range(min(len(li),len(l))):
    d[i+1][0] += b[i] - a[i]
    d[i+1][1] = min(k,t+i+1)
ans = 0
for i in range(len(li)+1):
    ans = max(ans, d[i][0]+d[i][1]**2)
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T