Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def modpow(a, b, mod=1):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a, b = a * a % mod, b // 2
    return ret


MOD = 10 ** 9 + 7
X, Y = map(int, input().split())
A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
if (X + Y) % 3 != 0 or A < 0 or B < 0:
    print(0)
else:
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD

print(ans)


Fixed submission:
MOD = 10 ** 9 + 7


def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
elif (2 * X - Y) // 3 < 0 or (2 * Y - X) // 3 < 0:
    print(0)
else:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
def modpow(a, b, mod=1):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


MOD = 10 ** 9 + 7
X, Y = map(int, input().split())

if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
elif (2 * X - Y) // 3 < 0 or (2 * Y - X) // 3 < 0:
    print(0)
else:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)


Fixed submission:
MOD = 10 ** 9 + 7


def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
    print(0)
elif (2 * X - Y) // 3 < 0 or (2 * Y - X) // 3 < 0:
    print(0)
else:
    A, B = (2 * X - Y) // 3, (2 * Y - X) // 3
    ans = 1
    for n in range(A + B, A, -1):
        ans = ans * n % MOD
    for n in range(1, B + 1):
        ans = ans * modpow(n, MOD - 2, MOD) % MOD
    print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)
T = [[- A[i] * F[i], A[i]] for i in range(N)]
heapq.heapify(T)

for _ in range(K):
    t, a = heapq.heappop(T)
    if t < 0:
        heapq.heappush(T, [(t // a) * (a - 1), a - 1])
    else:
        heapq.heappush(T, [0, 0])
        break

print(- heapq.heappop(T)[0])


Fixed submission:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)

minT, maxT = -1, max([A[i] * F[i] for i in range(N)])
while maxT - minT > 1:
    midT = minT + (maxT - minT) // 2
    if sum([max(A[i] - midT // F[i], 0) for i in range(N)]) > K:
        minT = midT
    else:
        maxT = midT

print(maxT)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += bisect.bisect_left(L[j + 1:], L[i] + L[j])

print(ans)


Fixed submission:
import bisect

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += bisect.bisect_left(L[j + 1:], L[i] + L[j])

print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret


A, B = map(int, input().split())
g = gcd(A, B)
print(len(set(trial_division(g))) + 1)


Fixed submission:
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    ret = [i for i in range(N + 1) if p[i]]
    return ret


def trial_division(N):
    factors = []
    for p in primes(int(N ** 0.5)):
        while N % p == 0:
            factors.append(p)
            N //= p
    if N > 1:
        factors.append(N)
    return factors


A, B = map(int, input().split())
g = gcd(A, B)
print(len(set(trial_division(g))) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans, tmp = 0, 0
for i in range(N):
    for j in range(N - i):
        if S[j] == S[i + j]:
            tmp += 1
        else:
            ans, tmp = max(ans, min(tmp, i)), 0
    ans, tmp = max(ans, min(tmp, i)), 0

print(ans)


Fixed submission:
N = int(input())
S = input()

ans, tmp = 0, 0
for i in range(N):
    for j in range(N - i):
        if S[j] == S[i + j]:
            tmp += 1
        else:
            ans, tmp = max(ans, min(tmp, i)), 0
    ans, tmp = max(ans, min(tmp, i)), 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum([i for i in range(N)]))


Fixed submission:
N = int(input())
print(N * (N - 1) // 2)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
AB, mx = [], [0] * (10 ** 1 + 1)
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))
    mx[A] = max(mx[A], B)

AB.sort(key=lambda x: x[1], reverse=True)
AB.sort(key=lambda x: x[0])

ans, idx, lAB = 0, 0, len(AB)
for i in range(1, M + 1):
    if AB[idx][0] <= i:
        while AB[idx][1] < mx[AB[idx][0] + 1]:
            tmp = AB[idx][0] + 1
            while not AB[idx][0] == tmp:
                idx += 1
        ans, idx = ans + AB[idx][1], idx + 1

print(ans)


Fixed submission:
import heapq
maxB = 10 ** 1

N, M = map(int, input().split())
AB = []
for _ in range(N):
    A, B = map(int, input().split())
    AB.append((maxB - B, A))

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

ans, heap, idx, lAB = 0, [], 0, len(AB)
for i in range(M):
    while idx < lAB and AB[idx][1] <= i + 1:
        heapq.heappush(heap, AB[idx])
        idx += 1
    if len(heap) > 0:
        ans += maxB - heapq.heappop(heap)[0]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def bellman_ford(v, G, confirm=False):
    ret = [10 ** 10] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1 if not confirm else (len(G) - 1) * 2):
        for u, g in enumerate(G):
            for w, l in g:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    return ret


N, M, P = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    G[A - 1].append((B - 1, - C + P))

ans = bellman_ford(0, G)[-1]
if ans == bellman_ford(0, G, True)[-1]:
    print(max(-ans, 0))
else:
    print('-1')


Fixed submission:
def bellman_ford(v, G):
    import copy
    INF = 10 ** 10
    ret = [INF] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[w] == INF and ret[w] > ret[u] + l:
                    ret[w] = -INF

    return ret


N, M, P = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    G[A - 1].append((B - 1, - C + P))

ans = bellman_ford(0, G)[-1]
print("-1" if ans == -10 ** 10 else max(-ans, 0))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
qTable = [[(j * i) % 13 for j in range(13)] for i in range(11)]

S = input()

C, tC, qi = [1] + [0] * 12, [0] * 13,  1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = qTable[j][qi]
            for c in range(13):
                tC[(c + q) % 13] += C[c]
    else:
        q = qTable[int(S[-(i + 1)])][qi]
        for c in range(13):
            tC[(c + q) % 13] = C[c]

    qi = qTable[10][qi]
    for c in range(13):
        C[c] = tC[c] % MOD

print(C[5] % MOD)


Fixed submission:
MOD = 10 ** 9 + 7
qTable = [[(j * i) % 13 for j in range(13)] for i in range(11)]

S = input()

C, tC, qi = [1] + [0] * 12, [0] * 13,  1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = qTable[j][qi]
            for c in range(13):
                tC[(c + q) % 13] += C[c]
    else:
        q = qTable[int(S[-(i + 1)])][qi]
        for c in range(13):
            tC[(c + q) % 13] = C[c]

    qi = qTable[10][qi]
    for c in range(13):
        C[c] = tC[c] % MOD

print(C[5] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()

C, qi = [1] + [0] * 12, 1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = (j * qi) % 13
            for c in range(13):
                tC[(c + q) % 13] += C[c]
        C = tC
    else:
        q, tC = (int(S[-(i + 1)]) * qi) % 13, [0] * 13
        for c in range(13):
            tC[(c + q) % 13] = C[c]
        C = tC
    qi = (qi * 10) % 13

print(C[5] % (10 ** 9 + 7))


Fixed submission:
MOD = 10 ** 9 + 7
qTable = [[(j * i) % 13 for j in range(13)] for i in range(11)]

S = input()

C, tC, qi = [1] + [0] * 12, [0] * 13,  1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = qTable[j][qi]
            for c in range(13):
                tC[(c + q) % 13] += C[c]
    else:
        q = qTable[int(S[-(i + 1)])][qi]
        for c in range(13):
            tC[(c + q) % 13] = C[c]

    qi = qTable[10][qi]
    for c in range(13):
        C[c] = tC[c] % MOD

print(C[5] % MOD)
Buggy python submission (verdict: Runtime Error):
import math
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
B, R = K, N - K


def f(n):
    return math.factorial(n)


for i in range(K):
    print(f(R + 1) // f(R - i) // f(i + 1)
          * (f(B - 1) // f(B - i - 1) // f(i)) % MOD)


Fixed submission:
import math
MOD = 10 ** 9 + 7

N, K = map(int, input().split())


def f(n):
    return math.factorial(n)


for i in range(K):
    if N - K - i >= 0:
        print(f(N - K + 1) // f(N - K - i) // f(i + 1)
              * (f(K - 1) // f(K - i - 1) // f(i)) % MOD)
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = ["#" * (W + 2)] + ["#" + input() + "#" for _ in range(H)] + ["#" * (W + 2)]

L = [[0] * (W + 2) for _ in range(H + 2)]
R = [[0] * (W + 2) for _ in range(H + 2)]
U = [[0] * (W + 2) for _ in range(H + 2)]
D = [[0] * (W + 2) for _ in range(H + 2)]

for h in range(H):
    for w in range(W):
        if S[h + 1][w + 1] == '.':
            L[h + 1][w + 1] = L[h + 1][w] + 1
            U[h + 1][w + 1] = U[h][w + 1] + 1
        if S[H - h][W - w] == '.':
            R[H - h][W - w] = R[H - h][W - w + 1] + 1
            D[H - h][W - w] = D[H - h + 1][W - w] + 1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(L[h + 1][w + 1] + R[h + 1][w + 1]
                  + U[h + 1][w + 1] + D[h + 1][w + 1] - 3, ans)

print(ans)


Fixed submission:
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-(h + 1)] = (D[-h] + 1) * S[-(h + 1)]

for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -(w + 1)] = (R[:, -w] + 1) * S[:, -(w + 1)]

print(np.max(U + D + L + R) - 3)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [input() for _ in range(H)]


def dfs(h, w):
    ans = 0
    for hp in range(h - 1, 0 - 1, -1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w - 1, 0 - 1, -1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    for hp in range(h + 1, H, 1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w + 1, W, 1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    return ans + 1


ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(dfs(h, w), ans)

print(ans)


Fixed submission:
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-(h + 1)] = (D[-h] + 1) * S[-(h + 1)]

for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -(w + 1)] = (R[:, -w] + 1) * S[:, -(w + 1)]

print(np.max(U + D + L + R) - 3)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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.sort(reverse=True, key=lambda x: x[1])

ans, i = 0, 0
for bc in BC:
    ti = bisect.bisect(A[i:], bc[1]) + i
    if (ti > i) and (bc[0] >= (ti - i)):
        ans += bc[1] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        ans += bc[1] * bc[0]
        i = i + bc[0]

print(ans + sum(A[i:]))


Fixed submission:
import bisect

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.sort(reverse=True, key=lambda x: x[1])

ans, i = 0, 0
for bc in BC:
    ti = bisect.bisect(A, bc[1])
    if (ti > i) and (bc[0] >= (ti - i)):
        ans += bc[1] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        ans += bc[1] * bc[0]
        i = i + bc[0]

print(ans + sum(A[i:]))

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

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.sort(reverse=True, key=lambda x: x[1])

i = 0
for bc in BC:
    ti = bisect.bisect(A[i:], bc[1]) + i
    if (ti > i) and (bc[0] >= (ti - i)):
        A[i:ti] = [bc[1]] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        A[i:i + bc[0]] = [bc[1]] * bc[0]
        i = i + bc[0]

print(sum(A))


Fixed submission:
import bisect

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.sort(reverse=True, key=lambda x: x[1])

ans, i = 0, 0
for bc in BC:
    ti = bisect.bisect(A, bc[1])
    if (ti > i) and (bc[0] >= (ti - i)):
        ans += bc[1] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        ans += bc[1] * bc[0]
        i = i + bc[0]

print(ans + sum(A[i:]))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

E = []
for i in range(X):
    for j in range(Y):
        E.append(A[i] + B[j])
E.sort(reverse=True)

F = []
for i in range(min(X * Y, K)):
    for j in range(Z):
        F.append(E[i] + C[j])
F.sort(reverse=True)

for i in range(K):
    print(F[i])


Fixed submission:
# -*- coding: utf-8 -*-

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)

Comb = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            Comb.append(A[i] + B[j] + C[k])

Comb.sort(reverse=True)
for i in range(K):
    print(Comb[i])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True) + [0]
B = sorted(list(map(int, input().split())), reverse=True) + [0]
C = sorted(list(map(int, input().split())), reverse=True) + [0]

E = []
for i in range(X):
    for j in range(Y):
        E.append(A[i] + B[j])
E.sort(reverse=True)

F = []
for i in range(min(X * Y, K)):
    for j in range(Z):
        F.append(E[i] + C[j])
F.sort(reverse=True)

for i in range(K):
    print(F[i])


Fixed submission:
# -*- coding: utf-8 -*-

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)

Comb = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            Comb.append(A[i] + B[j] + C[k])

Comb.sort(reverse=True)
for i in range(K):
    print(Comb[i])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

import bisect

N, Q = map(int, input().split())
S = input()

for _ in range(Q):
    l, r = map(int, input().split())
    print(S[(l - 1):r].count("AC"))


Fixed submission:
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()

S = S.replace("AC", "-+")
Sl = [0]
Sr = [0]
l = 0
r = 0
for i in range(N):
    if S[i] == "-":
        l += 1
    if S[i] == "+":
        r += 1
    Sl.append(l)
    Sr.append(r)

for _ in range(Q):
    l, r = map(int, input().split())
    print(Sr[r] - Sl[l - 1])
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N = int(input())

dp = {b: 1 for b in "ACGT"}
for _ in range(N - 1):
    dp_new = {}
    for k in dp:
        for b in "ACGT"
           if k[-2:] + b in ("AGC", "ACG", "GAC") or k[-3:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                dp_new[k[-3:] + b] += dp[k]
    dp = dp_new

mod = 10 ** 9 + 7
print(sum(dp.values()) % mod)


Fixed submission:
# -*- coding: utf-8 -*-

import itertools
comb = list(map(''.join, itertools.product("ACGT", repeat=4)))

mod = int(1e9) + 7

N = int(input())

dp = {c: [0, 0] for c in comb}
dp["TTTT"] = [1, 0]

for _ in range(N):
    dp_new = {c: [0, 0] for c in comb}
    for k in dp:
        for b in "ACGT":
            if k[2:4] + b in ("AGC", "ACG", "GAC") or k[1:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                dp_new[k[1:4] + b][1] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
            else:
                dp_new[k[1:4] + b][0] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
    dp = dp_new


print((4 ** N - sum([dp[k][1] for k in dp])) % mod)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = list(map(int, input().split()))

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))


Fixed submission:
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = list(map(int, input().split()))

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = list(map(int, input().split()))

cost = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
cd = {}
for a in A:
    if cost[a] in cd:
        cd[cost[a]] = max(cd[cost[a]], a)
    else:
        cd[cost[a]] = a

dp = [(0, [])]
for i in range(1, N + 1):
    mx, mxl, mxs = int(-1e10), [], ""
    for c in cd:
        if i - c >= 0 and mx <= dp[i - c][0] + 1 and 0 <= dp[i - c][0] and mxs <= ''.join(map(str, sorted(dp[i - c][1], reverse=True))):
            mx, mxl = dp[i - c][0] + 1, dp[i - c][1] + [cd[c]]
            mxs = ''.join(map(str, sorted(dp[i - c][1], reverse=True)))
    dp.append((mx, mxl))

ans = dp[-1][1]
print(''.join(map(str, sorted(ans, reverse=True))))


Fixed submission:
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = list(map(int, input().split()))

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
cK = K

digit_K = int(math.log(K, 2)) + 1 if not K == 0 else 0
d1s = [0]*digit_K
gain, Kgain = [], []

ans = sum(A)
for i in range(digit_K):
    for j in range(N):
        d1s[i] += A[j] % 2
        A[j] = A[j] // 2
    cK, dK = divmod(cK, 2)
    gain.append((N - digit1s[di] * 2) * 2**i if N - digit1s[di] * 2 else 0)
    Kgain.append((N - digit1s[di] * 2) * 2**i * dK)

maxgain = sum(Kgain)
for i in range(digit_K):
    K, dK = divmod(K, 2)
    if dK == 1:
        sumgain = sum(pgain[:i] + Kgain[i+1:])
    elif dK == 0:
        sumgain = sum(pgain[:i+1] + Kgain[i+1:])
    maxgain = max(maxgain, sumgain)

ans += maxgain

print(ans)


Fixed submission:
# -*- coding: utf-8 -*-
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))

digit_K = int(math.log(K, 2)) + 1 if not K == 0 else 0
d1s = [0]*digit_K
gain = []

ans = sum(A)
for i in range(digit_K):
    for j in range(N):
        d1s[i] += A[j] % 2
        A[j] = A[j] // 2
    gain.append((N - d1s[i] * 2) * 2**i)

pGain = [max(g, 0) for g in gain]
cK, kGain = K, []
for i in range(digit_K):
    cK, dK = divmod(cK,2)
    kGain.append(pGain[i] * dK)

maxgain = sum(kGain)
for i in range(digit_K):
    K, dK = divmod(K, 2)
    if dK == 1:
        sumgain = sum(pGain[:i] + kGain[i+1:])
        maxgain = max(maxgain, sumgain)

ans += maxgain
print(ans)