Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 10 ** 9 + 7

r1, c1, r2, c2 = map(int, input().split())

mc = ModComb(r2 + c2 + 10)
def f(i, j):
    return mc.nCk(i + j, i)

print((f(r2 + 1, c2 + 1) - f(r2 + 1, c1) - f(r1, c2 + 1) + f(r1, c1)) % mod)

Fixed submission:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 10 ** 9 + 7

r1, c1, r2, c2 = map(int, input().split())

mc = ModComb(r2 + c2 + 10)
def f(i, j):
    return mc.nCk(i + j, i)

print((f(r2 + 1, c2 + 1) - f(r2 + 1, c1) - f(r1, c2 + 1) + f(r1, c1)) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = i + a if i + a < H else H
        dp[idx] = dp[idx] if dp[idx] < dp[i] + b else dp[i] + b

print(dp[H])

Fixed submission:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = min(i + a, H)
        dp[idx] = min(dp[idx], dp[i] + b)

print(dp[H])

Fixed submission:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * (H + max(AB[::2]))

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Fixed submission:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] * (H + 10 ** 4 + 10)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(AB)] * 2))

print(min(dp[H:]))

Fixed submission:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Fixed submission:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):

import sys
sys.setrecursionlimit(200200)

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

def dfs(u, p):
    X[p] = 1 + sum(dfs(v, c) for v, c in E[u] if p != c)
    return X[p]

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = (I[N] + 1) * (N - 1) - inv * N - I[N] + 1
for e in range(N - 1):
    ans -= I[X[e]] + I[N - X[e]]
    ans %= mod

print(ans)

Fixed submission:
from itertools import accumulate

MAX = 2 * 10 ** 5 + 5

N, M, *A = map(int, open(0).read().split())

B = [0] * MAX
for a in A:
    B[a] += 1

C = list(accumulate(reversed(B)))[::-1]

ng, ok = 1, MAX
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    if sum(C[max(0, m - a)] for a in A) >= M:
        ng = m
    else:
        ok = m

D = list(accumulate(reversed(list(i * b for i, b in enumerate(B)))))[::-1]
print(sum(D[max(0, ng - a)] - (ng - a) * C[max(0, ng - a)] for a in A) + ng * M)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200200)

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

def dfs(u, p):
    X[p] = 1 + sum(dfs(v, c) for v, c in E[u] if p != c)
    return X[p]

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = (I[N] + 1) * (N - 1) - inv * N - I[N] + 1
for e in range(N - 1):
    ans -= I[X[e]] + I[N - X[e]]
    ans %= mod

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(200200)

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

visited = [False] * N
visited[0] = True

def dfs(u, i):
    res = 1
    for v, c in E[u]:
        if not visited[v]:
            visited[v] = True
            res += dfs(v, c)
    X[i] = res
    return res

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = (I[N] + 1) * (N - 1) - inv * N - I[N] + 1
for xe in range(N - 1):
    ans -= I[X[xe]] + I[N - X[xe]]
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

B = [0] * 62
for a in A:
    for i in range(62):
        if a >> i & 1:
            B[i] += 1

ans = 0
for i, b in enumerate(B):
    ans += ((N - b) * b % mod) * pow(2, i, mod)
    ans %= mod

print(ans)


Fixed submission:
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

B = [0] * 62
for a in A:
    for i in range(62):
        if a >> i & 1:
            B[i] += 1

ans = 0
for i, b in enumerate(B):
    ans += ((N - b) * b % mod) * pow(2, i, mod)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

N = int(input())
S = input()

cnt = 0
for i, j, k in product("0123456789", repeat=3):
    T = [i, j, k]
    cur = 0
    for s in S:
        if s == T[cur]:
            cur += 1
            if cur == 3:
                cnt += 1
                break

print(cnt)


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

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))

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

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))


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

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))
Buggy python submission (verdict: Runtime Error):
from functools import reduce

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    mod_mul = lambda a, b: a * b % mod
    numer = reduce(mod_mul, range(n - k + 1, n + 1))
    denom = reduce(mod_mul, range(1, k + 1))
    return numer * pow(denom, mod - 2, mod) % mod

X, Y = map(int, input().split())

b = (2 * X - Y) // 3
a = (-X + 2 * Y) // 3

if (X + Y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    print(nCk(a + b, a))


Fixed submission:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 10 ** 9 + 7
mc = ModComb(3 * 10 ** 6, mod)

X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (X - 2 * Y) % 3 != 0:
    print(0)
    quit()

b = (2 * X - Y) // 3
a = (-X + 2 * Y) // 3

print(mc.nCk(a + b, a))
Buggy python submission (verdict: Runtime Error):
from numpy import*
(N,T),*L=loadtxt(open(0)).tolist()
d=zeros(1e4,int)
for w,v in sorted(L):t=d[w:T+w];s=d[:T]+v;t[t<s]=s
print(max(d))

Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
from numpy import*
N,T,*L=int_(open(0).read().split())
d=[0]*6010
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, T, *AB = map(int, open(0).read().split())

    dp = [0] * 6010
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        for i in reversed(range(T)):
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()

Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, T, *AB = map(int, open(0).read().split())

    dp = [0] * (T + max(AB[::2]))
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        for i in reversed(range(T)):
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()

Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))


Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))


Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K, *I = map(int, open(0).read().split())
    A, F = I[:N], I[N:]

    A.sort()
    F.sort(reverse=True)

    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if sum(max(0, a - mid // f) for a, f in zip(A, F)) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, K, *I = map(int, open(0).read().split())
    A, F = I[:N], I[N:]

    A.sort()
    F.sort(reverse=True)

    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if sum(max(0, a - mid // f) for a, f in zip(A, F)) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N, *D = map(int, open(0).read().split())

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += D[i] * D[j]

print(ans)


Fixed submission:
from itertools import groupby

N = int(input())
S = input()

G = [len(tuple(v)) for k, v in groupby(S)]
print(len(G))
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right

N, *L = map(int, open(0).read().split())

L.sort()

cnt = 0
for i in range(1, N - 1):
    b = L[i]
    for j in range(i):
        a = L[j]
        l, r = bisect_left(L, b - a + 1, lo=i), bisect_right(L, a + b - 1, lo=i)
        cnt += r - l - (l <= i <= r) - (l <= j <= r)

print(cnt)


Fixed submission:
from bisect import bisect_left, bisect_right

N, *L = map(int, open(0).read().split())

L.sort()

cnt = 0
for i in range(1, N - 1):
    b = L[i]
    for j in range(i):
        a = L[j]
        l, r = bisect_left(L, b - a + 1, lo=i), bisect_right(L, a + b - 1, lo=i)
        cnt += r - l - (l <= i <= r) - (l <= j <= r)

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = float("inf")

N, M, L, *I = map(int, open(0).read().split())
ABC, ST = I[:3 * M], I[3 * M + 1:]

E = [[INF] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a - 1][b - 1] = E[b - 1][a - 1] = c


E = WarshallFloyd(E)

for i in range(N):
    for j in range(N):
        if E[i][j] <= L:
            E[i][j] = 1
        else:
            E[i][j] = INF

E = WarshallFloyd(E)

for s, t in zip(*[iter(ST)] * 2):
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else a)


Fixed submission:
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
E = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)

for i in range(N):
    for j in range(N):
        E[i][j] = (E[i][j] <= L)

E = floyd_warshall(E)

INF = float("inf")

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else int(a))

Buggy python submission (verdict: Time Limit Exceeded):
def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = float("inf")

N, M, L = map(int, input().split())
E = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c


E = WarshallFloyd(E)

for i in range(N):
    for j in range(N):
        if E[i][j] <= L:
            E[i][j] = 1
        else:
            E[i][j] = INF

E = WarshallFloyd(E)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else a)


Fixed submission:
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
E = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)

for i in range(N):
    for j in range(N):
        E[i][j] = (E[i][j] <= L)

E = floyd_warshall(E)

INF = float("inf")

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else int(a))
Buggy python submission (verdict: Runtime Error):
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def primes(n):
    memo = [True] * (n + 1)
    i = 2
    while i * i <= n:
        if memo[i]:
            j = i << 1
            while j <= n:
                memo[j] = False
                j += i
        i += 1
    return {i for i in range(n + 1) if memo[i] and i >= 2}

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

if A > B:
    A, B = B, A

D = set(primes(A))
E = {d for d in divisors(A) if B % d == 0}

print(len(D & E) + 1)


Fixed submission:
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def is_prime(N):
    if N < 2 or N % 2 == 0:
        return (N == 2)
    i = 3
    while i * i <= N:
        if N % i == 0:
            return False
        i += 2
    return True

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

if A > B:
    A, B = B, A

D = divisors(A)

ans = 0
for d in D:
    if B % d == 0 and is_prime(d):
        ans += 1

print(ans + 1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = float("inf")

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

dp = [INF] * (2 ** N)
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i in range(len(dp)):
        dp[i | mask] = min(dp[i | mask], dp[i] + a)

ans = dp[-1]
print(-1 if ans == INF else ans)


Fixed submission:
INF = float("inf")

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

dp = [INF] * (2 ** N)
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i in range(len(dp)):
        if dp[i | mask] > dp[i] + a:
            dp[i | mask] = dp[i] + a

ans = dp[-1]
print(-1 if ans == INF else ans)
Buggy python submission (verdict: Time Limit Exceeded):
def lcp(S):
    N = len(S)
    prefix = [0] * N
    j = 0
    for i in range(1, N):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < N and S[k] == S[i + k]:
                k += 1
            prefix[i] = k
            j = i
    prefix[0] = N
    return prefix

N = int(input())
S = input()

ans = 0
for j in range(N):
    prefix = lcp(S[j:])
    for i, p in enumerate(prefix):
        if p <= i:
            ans = max(ans, p)
print(ans)



Fixed submission:
def lcp(S):
    N = len(S)
    prefix = [0] * N
    j = 0
    for i in range(1, N):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < N and S[k] == S[i + k]:
                k += 1
            prefix[i] = k
            j = i
    prefix[0] = N
    return prefix

N = int(input())
S = input()

ans = 0
for j in range(N):
    prefix = lcp(S[j:])
    for i, p in enumerate(prefix):
        if p <= i:
            ans = max(ans, p)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)
    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[len(S)][5])

Fixed submission:
mod = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)
    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[len(S)][5])