Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ans = 0

for i in range(N):
    a = L[i]
    for ii in range(i + 1, N):
        b = L[ii]
        for iii in range(N - 1, ii, -1):
            c = L[iii]
            if a >= b + c:
                continue
            ans += iii - ii
            break

print(ans)

Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N - 2):
    a = L[i]
    for ii in range(i + 1, N - 1):
        b = L[ii]
        iii = bisect.bisect_left(L, a + b)
        ans += iii - ii - 1
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))

ans = 0

for i in range(N):
    for ii in range(i + 1, N):
        for iii in range(ii + 1, N):
            if L[i] + L[ii] > L[iii] and \
                L[i] + L[iii] > L[ii] and \
                L[ii] + L[iii] > L[i]:
                ans += 1

print(ans)

Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N - 2):
    a = L[i]
    for ii in range(i + 1, N - 1):
        b = L[ii]
        iii = bisect.bisect_left(L, a + b)
        ans += iii - ii - 1
            
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
i = 2
while True:
    if C == 1:
        break
    if C % i != 0:
        i += 1
        continue
    ans.append(i)
    C //= i
print(len(set(ans)) + 1)


Fixed submission:
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
i = 2
while True:
    if C == 1:
        break
    if C % i != 0:
        i += 1
        continue
    ans.append(i)
    C //= i
print(len(set(ans)) + 1)


Fixed submission:
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
for i in range(2, 10 ** 12 + 1):
    if C == 1:
        break
    while True:
        if C % i != 0:
            break
        ans.append(i)
        C //= i
print(len(set(ans)) + 1)


Fixed submission:
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
for i in range(2, 10 ** 12 + 1):
    if C == 1:
        break
    while True:
        if C % i != 0:
            break
        if i not in ans:
            ans.append(i)
        C //= i
print(len(ans) + 1)


Fixed submission:
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()


Fixed submission:
def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, L = map(int, input().split())
    a = sum([L + n for n in range(N)])
    if L > 0:
        print(a - a[0])
    elif abs(L) >= N:
        print(a - a[-1])
    else:
        print(a)


main()


Fixed submission:
def main():
    N, L = map(int, input().split())
    a = [L + n for n in range(N)]
    if L > 0:
        print(sum(a) - a[0])
    elif abs(L) >= N:
        print(sum(a) - a[-1])
    else:
        print(sum(a))


main()
Buggy python submission (verdict: Runtime Error):
import math


def main():
    A, B, C, D = map(int, input().split())
    lcm = (C * D) // math.gcd(C, D)
    bc = B // C
    ac = A // C
    if A % C == 0:
        ac -= 1
    bd = B // D
    ad = A // D
    if A % D == 0:
        ad -= 1
    blcm = B // lcm
    alcm = A // lcm
    if A % lcm == 0:
        alcm -= 1
    print(B - A + 1 - ((bc - ac) + (bd - ad) - (blcm - alcm)))


main()


Fixed submission:
import fractions


def main():
    A, B, C, D = map(int, input().split())
    lcm = (C * D) // fractions.gcd(C, D)
    bc = B // C
    ac = A // C
    if A % C == 0:
        ac -= 1
    bd = B // D
    ad = A // D
    if A % D == 0:
        ad -= 1
    blcm = B // lcm
    alcm = A // lcm
    if A % lcm == 0:
        alcm -= 1
    print(B - A + 1 - ((bc - ac) + (bd - ad) - (blcm - alcm)))


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if i in A:
            continue
        elif i + 1 in A:
            dp[i] = dp[i + 2]
        elif i + 2 in A:
            dp[i] = dp[i + 1]
        elif i + 1 in A and i + 2 in A:
            break
        else:
            dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    A = [0] * (N + 2)
    for _ in range(M):
        A[int(input())] = 1
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if A[i] == 1:
            continue
        dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()
Buggy python submission (verdict: Runtime Error):
def f(s, v, k):
    if k == 0:
        return sum(s)
    v1 = v[::]
    s1 = s[::]
    v2 = v[::]
    s2 = s[::]
    v3 = v[::]
    s3 = s[::]
    s3.append(v3.pop(0))
    v4 = v[::]
    s4 = s[::]
    s4.append(v4.pop(-1))
    a = -1 * (10 ** 7)
    b = -1 * (10 ** 7)
    if len(s) > 0:
        ms = min(s)
        v1.insert(0, ms)
        s1.pop(s1.index(ms))
        v2.append(ms)
        s2.pop(s2.index(ms))
        a = f(s1, v1, k - 1)
        b = f(s2, v2, k - 1)
    c = f(s3, v3, k - 1)
    d = f(s4, v4, k - 1)
    return max(a, b, c, d)


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = max(f([V[0]], V[1:], K - 1), f([V[-1]], V[:-1], K - 1))
    if ans > 0:
        print(ans)
    else:
        print(0)


main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0
    for l in range(K + 1):
        for r in range(K - l + 1):
            if l + r > N:
                continue
            d = K - l - r
            s = V[:l] + V[N - r:N]
            now = 0
            now += sum(s)
            s.sort()
            for i in range(d):
                if i >= len(s):
                    break
                if s[i] > 0:
                    break
                now -= s[i]
            ans = max(ans, now)
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = [0] * N
    for _ in range(M):
        L, R = map(int, input().split())
        for i in range(L - 1, R):
            A[i] += 1
    print(A.count(M))


main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    A = [0] * (N + 1)
    for _ in range(M):
        L, R = map(int, input().split())
        A[L - 1] += 1
        A[R] -= 1
    c = 0
    ans = 0
    for i, a in enumerate(A):
        c += a
        if c == M:
            ans += 1
    print(ans)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    BC = []
    for _ in range(M):
        B, C = map(int, input().split())
        BC.append((B, C))
    BC = sorted(BC, key=lambda x: x[1], reverse=True)
    i = 0
    for b, c in BC:
        for _ in range(b):
            if A[i] >= c:
                break
            A[i] = c
            i += 1
    print(sum(A))


main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    BC = []
    for _ in range(M):
        B, C = map(int, input().split())
        BC.append((B, C))
    BC = sorted(BC, key=lambda x: x[1], reverse=True)
    i = 0
    for b, c in BC:
        for _ in range(b):
            if i >= len(A) or A[i] >= c:
                break
            A[i] = c
            i += 1
    print(sum(A))


main()
Buggy python submission (verdict: Time Limit Exceeded):
import decimal


def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = n
        c = 1
        while K > s:
            s *= 2
            c /= 2
        ans += decimal.Decimal((1 / N) * c)
    print(ans)


main()


Fixed submission:
import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import decimal


def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 1
        while K > s:
            s *= 2
            c /= 2
        ans += decimal.Decimal((1 / N) * c)
    print(ans)


main()


Fixed submission:
import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import decimal


def main():
    N, K = map(int, input().split())
    s = N
    c = 0
    while K > s:
        s *= 2
        c += 1
    cp = (1 / 2) ** c
    ans = decimal.Decimal((1 / N) * cp)
    cc = c
    for n in range(N - 1, 0, -1):
        s = n
        c = 0
        while K > s:
            s *= 2
            c += 1
        cp *= 1 / 2 ** (c - cc)
        ans += decimal.Decimal((1 / N) * cp)
        cc = c
    print(ans)


main()


Fixed submission:
import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import decimal


def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)


main()


Fixed submission:
import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    S = input()
    nums = []
    now = 1
    cnt = 0
    for s in S:
        if int(s) == now:
            cnt += 1
        else:
            nums.append(cnt)
            now ^= 1
            cnt = 1
    if cnt > 0:
        nums.append(cnt)
    if len(nums) % 2 == 0:
        nums.append(0)
    add = 2 * K + 1
    ans = 0
    for cnt in range(0, len(nums), 2):
        tmp = 0
        left = cnt
        right = min(cnt + add, len(nums))
        for j in range(left, right):
            tmp += nums[j]
        ans = max(tmp, ans)
    print(ans)


main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    S = input()
    nums = []
    now = 1
    cnt = 0
    for s in S:
        if int(s) == now:
            cnt += 1
        else:
            nums.append(cnt)
            now ^= 1
            cnt = 1
    if cnt > 0:
        nums.append(cnt)
    if len(nums) % 2 == 0:
        nums.append(0)
    add = 2 * K + 1
    ans = 0
    left = 0
    right = 0
    tmp = 0
    for cnt in range(0, len(nums), 2):
        nleft = cnt
        nright = min(cnt + add, len(nums))
        while nleft > left:
            tmp -= nums[left]
            left += 1
        while nright > right:
            tmp += nums[right]
            right += 1
        ans = max(tmp, ans)
    print(ans)


main()
Buggy python submission (verdict: Runtime Error):
import math


def main():
    ans = 0
    t = []
    for _ in range(5):
        x = input()
        if x[-1] == '0':
            ans += int(x)
        else:
            t.append(int(x))
    t.sort(key=lambda x: str(x)[-1])
    for i in range(1, len(t)):
        ans += math.ceil(t[i] / 10) * 10
    ans += t[0]
    print(ans)


main()


Fixed submission:
import math


def main():
    ans = 0
    t = []
    for _ in range(5):
        x = input()
        if x[-1] == '0':
            ans += int(x)
        else:
            t.append(int(x))
    if len(t) > 0:
        t.sort(key=lambda x: str(x)[-1])
        for i in range(1, len(t)):
            ans += math.ceil(t[i] / 10) * 10
        ans += t[0]
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)
    L = []
    for a in A:
        for b in B:
            L.append(a + b)
    LL = []
    for ab in L:
        for c in C:
            LL.append(ab + c)
    for x in sorted(LL, reverse=True)[:K]:
        print(x)


main()


Fixed submission:
def main():
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)
    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)
    AB.sort(reverse=True)
    ABC = []
    for i in range(min(K, len(AB))):
        for c in C:
            ABC.append(AB[i] + c)
    ABC.sort(reverse=True)
    for x in ABC[:K]:
        print(x)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S) + 1)]
    c = 0
    for i in range(1, len(S)):
        if S[i - 1:i + 1] == 'AC':
            c += 1
            SL[i + 1:] = [c for _ in range(len(S) - i)]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r] - SL[l])
    for a in ans:
        print(a)


main()


Fixed submission:
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S))]
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            SL[i + 1] = SL[i] + 1
        else:
            SL[i + 1] = SL[i]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r - 1] - SL[l - 1])
    for a in ans:
        print(a)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S) + 1)]
    for i in range(1, len(S)):
        if S[i - 1:i + 1] == 'AC':
            SL[i] = 1
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        s = sum(SL[l:r])
        ans.append(s)
    for a in ans:
        print(a)


main()


Fixed submission:
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S))]
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            SL[i + 1] = SL[i] + 1
        else:
            SL[i + 1] = SL[i]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r - 1] - SL[l - 1])
    for a in ans:
        print(a)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def f(a, x):
    i = 0
    j = len(a) - 1
    n = j // 2
    if a[0] >= x:
        return a[0]
    if x >= a[-1]:
        return a[-1]
    while j - i > 1:
        if x > a[n]:
            i = n
            n = i + (j - i) // 2
        else:
            j = n
            n = j // 2
    if x - a[i] > a[j] - x:
        return a[j]
    return a[i]


def main():
    A, B, Q = map(int, input().split())
    s = []
    t = []
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    for _ in range(Q):
        x = int(input())
        sx = f(s[::], x)
        tsx = f(t[::], sx)
        tx = f(t[::], x)
        stx = f(s[::], tx)
        ans.append(min(abs(sx - x) + abs(sx - tsx),
                       abs(tx - x) + abs(tx - stx)))
    for a in ans:
        print(a)


main()


Fixed submission:
import bisect

def main():
    A, B, Q = map(int, input().split())
    s = [-float('inf')]
    t = [-float('inf')]
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    s.append(float('inf'))
    t.append(float('inf'))
    for _ in range(Q):
        x = int(input())
        i = bisect.bisect_right(s, x)
        j = bisect.bisect_right(t, x)
        a = float('inf')
        for ss in [s[i - 1], s[i]]:
            for tt in [t[j - 1], t[j]]:
                a = min(a, abs(ss - x) + abs(tt - ss),
                        abs(tt - x) + abs(ss - tt))
        ans.append(a)
    for a in ans:
        print(a)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def f(a, x):
    a.append(x)
    a.sort()
    i = a.index(x)
    if 0 > i - 1:
        return a[i + 1]
    if i + 1 >= len(a):
        return a[i - 1]
    if a[i] - a[i - 1] > a[i + 1] - a[i]:
        return a[i + 1]
    return a[i - 1]


def main():
    A, B, Q = map(int, input().split())
    s = []
    t = []
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    for _ in range(Q):
        x = int(input())
        sx = f(s[::], x)
        tsx = f(t[::], sx)
        tx = f(t[::], x)
        stx = f(s[::], tx)
        ans.append(min(abs(sx - x) + abs(sx - tsx),
                       abs(tx - x) + abs(tx - stx)))
    for a in ans:
        print(a)


main()


Fixed submission:
import bisect

def main():
    A, B, Q = map(int, input().split())
    s = [-float('inf')]
    t = [-float('inf')]
    ans = []
    for _ in range(A):
        s.append(int(input()))
    for _ in range(B):
        t.append(int(input()))
    s.append(float('inf'))
    t.append(float('inf'))
    for _ in range(Q):
        x = int(input())
        i = bisect.bisect_right(s, x)
        j = bisect.bisect_right(t, x)
        a = float('inf')
        for ss in [s[i - 1], s[i]]:
            for tt in [t[j - 1], t[j]]:
                a = min(a, abs(ss - x) + abs(tt - ss),
                        abs(tt - x) + abs(ss - tt))
        ans.append(a)
    for a in ans:
        print(a)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    X = sorted(list(map(int, input().split())))

    if M == 1:
        print(0)
    elif N == 1:
        print(max(X) - min(X))
    else:
        dx = [abs(X[m] - X[m + 1]) for m in range(M - 1)]
        for _ in range(N - 1):
            dx.pop(dx.index(max(dx)))
        print(sum(dx))


main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    X = sorted(list(map(int, input().split())))

    if M == 1:
        print(0)
    elif N == 1:
        print(max(X) - min(X))
    else:
        if N > M:
            N = M
        dx = sorted([abs(X[m] - X[m + 1]) for m in range(M - 1)])
        print(sum(dx[:M - N]))


main()
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

N, K = map(int, input().split())
td = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = []
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        heappush(q, d)
    else:
        v.append(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = heappop(q)
        cnt += d + 2 * len(v) + 1 - x
        v.append(t)
        ans = max(ans, cnt)
print(ans)


Fixed submission:
from heapq import heappop, heappush

N, K = map(int, input().split())
td = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = set()
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        heappush(q, d)
    else:
        v.add(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = heappop(q)
        cnt += d + 2 * len(v) + 1 - x
        v.add(t)
        ans = max(ans, cnt)
print(ans)