Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not m:
        ans = max(ans, d)

print(ans)

Fixed submission:
N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not rems:
        ans = max(ans, d)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

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

print(dp[-1][5])

Fixed submission:
S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

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

print(dp[-1][5])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left
from collections import deque

N = int(input())
d = defaultdict(list)

for i in range(N):
    v = int(input())
    d[v].append(i)

keys = sorted(d.keys())
s = deque(d[keys[0]])

for k in keys[1:]:
    used = set()
    for i in d[k]:
        j = bisect_left(s, i)
        if 0<j<=len(s):
            if not s[j-1] in used:
                s[j-1] = i
            else:
                s = s[:j] + [i] + s[j:]
        elif j==0:
            s.appendleft(i)
        used |= {i}

print(len(s))

Fixed submission:
from collections import deque
from bisect import bisect_left

N = int(input())
d = deque([])
l = [int(input()) for _ in range(N)]

d.append(l[0])

for i in l[1:]:
    v = bisect_left(d, i)
    if v == 0:
        d.appendleft(i)
    else:
        d[v-1] = i

print(len(d))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

def f(N, K):
    for i in range(N+1):
        a = i*(i-1)//2
        for j in range(N+1):
            for k in range(N+1):
                if i+j+k+1==N and a+j+k==K:
                    return (i, j, k)
    return (-1, -1, -1)

i, j, k = f(N, K)
if i==-1 and j==-1 and k==-1:
    print(-1)
else:
    l = []
    for a in range(2, 2+i):
        l.append((1,a))

    p = a
    for a in range(p, p+j+1):
        l.append((a, a+1))
    p = a

    for a in range(p+j+1, N+1):
        for b in range(a+1, N+1):
            l.append((a,b))
    
    print(len(l))
    for a, b in l:
        print(a, b)

Fixed submission:
N, K = map(int, input().split())

amax = (N-1)*(N-2)//2
if amax-K>=0:
    print(amax-K+N-1)
    for i in range(N-1):
        print(1, i+2)
    cnt = 0

    def out(x):
        cnt = 0
        for i in range(2, N+1):
            for j in range(i+1, N+1):
                if cnt == amax-K:
                    return
                print(i, j)
                cnt += 1
    out(amax-K)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

N = int(input())
d = defaultdict(list)
cd = set()
D = 100000

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

used = [0]*(D+1)
ans = 0

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)


Fixed submission:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
cd = set()
D = 100000
used = [0]*(2*D+1)
ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*S, = map(int, input().split())
*T, = map(int, input().split())

dp = [[0]*(M+1) for _ in range(N+1)]
accum = [[0]*(M+1) for _ in range(N+1)]
MOD = 10**9+7

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = 0 if S[i-1]!=T[j-1] else 1 + accum[i-1][j-1]
        accum[i][j] = accum[i-1][j]+accum[i][j-1]-accum[i-1][j-1]+dp[i][j]   

ans = (sum(map(sum, dp))+1)%MOD
print(ans)


Fixed submission:
N, M = map(int, input().split())
*S, = map(int, input().split())
*T, = map(int, input().split())

dp = [[0]*(M+1) for _ in range(N+1)]
accum = [[0]*(M+1) for _ in range(N+1)]
MOD = 10**9+7

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = 0 if S[i-1]!=T[j-1] else (1 + accum[i-1][j-1])%MOD
        accum[i][j] = (accum[i-1][j]+accum[i][j-1]-accum[i-1][j-1]+dp[i][j])%MOD     

ans = (sum(map(sum, dp))+1)%MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
N, M = map(int, input().split())

mod = 10**9+7

a = [1] * (N+1)
for _ in range(M):
    a[int(input())] = 0

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))

Fixed submission:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
mod = 10**9+7

a = [1] * (N+1)
for _ in range(M):
    a[int(input())] = 0

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())

dw = [[0]*W for _ in range(H)]
dh = [[0]*W for _ in range(H)]
maze = [[0]*W for _ in range(H)]

for h in range(H):
    s = input()
    c = 0
    for w, ss in enumerate(s):
        maze[h][w] = ss
        if ss == ".":
            c += 1
            dw[h][w] = c
        else:
            c = 0

for w in range(W):
    c = 0
    for h in range(H):
        ss = maze[h][w]
        if ss == ".":
            c += 1
            dh[h][w] = c
        else:
            c = 0

for h in range(H):
    m = 0
    for w in range(W)[::-1]:
        if dw[h][w] == 0:
            m = 0
        else:
            m = max(m, dw[h][w])
            dw[h][w] = m

for w in range(W):
    m = 0
    for h in range(H)[::-1]:
        if dh[h][w] == 0:
            m = 0
        else:
            m = max(m, dh[h][w])
            dh[h][w] = m

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dh[h][w]+dw[h][w]-1)

print(ans)

Fixed submission:
H, W = map(int, input().split())

dw = [[0]*W for _ in range(H)]
dh = [[0]*W for _ in range(H)]
maze = [[0]*W for _ in range(H)]

for h in range(H):
    s = input()
    c = 0
    for w, ss in enumerate(s):
        maze[h][w] = ss
        if ss == ".":
            c += 1
            dw[h][w] = c
        else:
            c = 0

for w in range(W):
    c = 0
    for h in range(H):
        ss = maze[h][w]
        if ss == ".":
            c += 1
            dh[h][w] = c
        else:
            c = 0

for h in range(H):
    m = 0
    for w in range(W)[::-1]:
        if dw[h][w] == 0:
            m = 0
        else:
            m = max(m, dw[h][w])
            dw[h][w] = m

for w in range(W):
    m = 0
    for h in range(H)[::-1]:
        if dh[h][w] == 0:
            m = 0
        else:
            m = max(m, dh[h][w])
            dh[h][w] = m

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dh[h][w]+dw[h][w]-1)

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

ans = 1
for s in S:
    if s=="1":
        ans *= 2

a = 0
for i, s in enumerate(S, start=1):
    if s=="1":
        a += 1
        ans += (2**(a-1))*(3**(N-i))
        ans %= mod

print(ans%mod)

Fixed submission:
S = input()
N = len(S)
mod = 10**9+7
ans = pow(2, S.count("1"), mod)

a = 0
for i, s in enumerate(S, start=1):
    if s=="1":
        a += 1
        ans += pow(2, a-1, mod)*pow(3, N-i, mod)
        ans %= mod

print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
mod = 10**9+7

ans = 1
for s in S:
    if s=="1":
        ans *= 2

a = 0
for i, s in enumerate(S, start=1):
    if s=="1":
        a += 1
        ans += (2**(a-1))*(3**(N-i))
        ans %= mod

print(ans%mod)

Fixed submission:
S = input()
N = len(S)
mod = 10**9+7
ans = pow(2, S.count("1"), mod)

a = 0
for i, s in enumerate(S, start=1):
    if s=="1":
        a += 1
        ans += pow(2, a-1, mod)*pow(3, N-i, mod)
        ans %= mod

print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
S = list(S.replace("BC", "X"))
N = len(S)
pos = 1
ans = 0

c = True
while c:
    c = False
    pos = 1
    while pos<N:
        if S[pos-1]=="A" and S[pos]=="X":
            S[pos-1], S[pos] = S[pos], S[pos-1]
            c = True
            ans += 1
        pos += 1
print(ans)

Fixed submission:
S = list(input().replace("BC", "X"))
N = len(S)
pos, ans = 0, 0
ca = 0

while pos<N:
    ca = 0
    if S[pos]=="A" or S[pos]=="X":
        while pos<N and (S[pos]=="A" or S[pos]=="X"):
            if S[pos]=="A":
                ca += 1
            else:
                ans += ca
            pos += 1
    else:
        pos += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

V = defaultdict(list)
N = int(input())
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
*c, = map(int, input().split())
c.sort(reverse=True)

s = {}

cost = [-1]*(N+1)
p = 0
ans = 0
for v, l in sorted(V.items(),key=lambda x:-len(x[1])):
    print(cost[v], v, p, cost)
    if cost[v]==-1:
        cost[v] = c[p]
        p += 1

    for i in l:
        if cost[i]!=-1:continue
        cost[i] = c[p]
        s[(v, i)] = min(cost[i], cost[v])
        p += 1

print(sum(s.values()))
print(*cost[1:])

Fixed submission:
from collections import defaultdict

V = defaultdict(list)
N = int(input())
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
*c, = map(int, input().split())
c.sort(reverse=True)

root, _ = max(V.items(), key=lambda x:len(x[1]))
visited = [False] * (N+1)
identifier = [0] * (N+1)

p = 0
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    identifier[a] = p

    p+=1

    for i in V[a]:
        if visited[i]:continue
        q.append(i)

cost = 0
visited = [False] * (N+1)
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    p+=1

    for b in V[a]:
        if visited[b]:continue
        cost += min(c[identifier[a]], c[identifier[b]])
        q.append(b)

print(cost)
print(*[c[i] for i in identifier[1:]])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*A, = map(int, input().split())

for _ in range(M):
    B, C = map(int, input().split())
    A += [C]*B
A.sort(reverse=True)
print(sum(A[:N]))

Fixed submission:
N, M = map(int, input().split())
*A, = map(int, input().split())
A.sort()

l = []
for _ in range(M):
    B, C = map(int, input().split())
    l.append((B, C))
l.sort(key=lambda x:-x[1])

def solve():
    p = 0
    ans = 0
    for i, j in l:
        for _ in range(i):
            ans += max(A[p], j)
            p += 1
            if N==p:
                return ans
    
    for i in range(p, N):
        ans += A[i]
    return ans
    
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*A, = map(int, input().split())

for _ in range(M):
    B, C = map(int, input().split())
    A += [C]*B
A.sort(reverse=True)
print(sum(A[:N]))

Fixed submission:
N, M = map(int, input().split())
*A, = map(int, input().split())
A.sort()

l = []
for _ in range(M):
    B, C = map(int, input().split())
    l.append((B, C))
l.sort(key=lambda x:-x[1])

def solve():
    p = 0
    ans = 0
    for i, j in l:
        for _ in range(i):
            ans += max(A[p], j)
            p += 1
            if N==p:
                return ans
    
    for i in range(p, N):
        ans += A[i]
    return ans
    
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
d = {i:0 for i in range(N+1)}

for i in range((N//G)+1):
    for j in range((N//B)+1):
        if i*G+j*B<=N:
            d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)

Fixed submission:
from collections import defaultdict

R, G, B, N = map(int, input().split())
d = defaultdict(int)

for i in range((N//G)+1):
    for j in range((N//B)+1):
        d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

R, G, B, N = map(int, input().split())
d = defaultdict(int)

for i in range((N//G)+1):
    for j in range((N//B)+1):
        d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)

Fixed submission:
from collections import defaultdict

R, G, B, N = map(int, input().split())
d = defaultdict(int)

for i in range((N//G)+1):
    for j in range((N//B)+1):
        d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def dfs(V, start):
    q = [(start, 0)]
    used = [False] * (n+1)
    farthest = 0
    pos = 0

    while q:
        s, cost = q.pop()
        if farthest < cost:
            pos = s
            farthest = cost
        used[s] = True
        for t, c in V[s].items():
            if used[t]:
                continue
            q.append((t, cost + c))
    
    return farthest, pos


if __name__ == "__main__":
    n = int(input())
    V = {i:dict() for i in range(1, n+1)}

    for _ in range(n - 1):
        s, t = map(int, input().split())
        V[s][t] = 1
        V[t][s] = 1

    d = dfs(V, dfs(V, 1)[1])[0]
    if d==0:
        print("First")
    elif d==1:
        print("Second")
    elif d==2:
        print("First")
    elif (d-1)%3==0:
        print("Second")
    else:
        print("First")


Fixed submission:
import sys
input = sys.stdin.readline


def dfs(V, start):
    q = [(start, 0)]
    used = [False] * (n+1)
    farthest = 0
    pos = 0

    while q:
        s, cost = q.pop()
        if farthest < cost:
            pos = s
            farthest = cost
        used[s] = True
        for t, c in V[s].items():
            if used[t]:
                continue
            q.append((t, cost + c))
    
    return farthest, pos


if __name__ == "__main__":
    n = int(input())
    V = {i:dict() for i in range(1, n+1)}

    for _ in range(n - 1):
        s, t = map(int, input().split())
        V[s][t] = 1
        V[t][s] = 1

    if n==1:
        print("First")
    else:
        d = dfs(V, dfs(V, 1)[1])[0]
        if d==1:
            print("Second")
        elif d==2:
            print("First")
        elif (d-1)%3==0:
            print("Second")
        else:
            print("First")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())
l = [(i, j) for i,j in zip(V, C)]

ans = -10**12
for i in p(range(2), repeat=N):
    X, Y = 0, 0
    for j, k in enumerate(i):
        if k==1:
            X += V[j]
            Y += C[j]
    ans = max(ans, X-Y)
print(ans)

Fixed submission:
from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())

ans = 0
for a in p(range(2), repeat=N):
    X, Y = 0, 0
    for i, j in enumerate(a):
        if j:
            X+=V[i]
            Y+=C[i]
    ans = max(ans, X-Y)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())

ans = 0
for a in p(range(2), repeat=N):
    X, Y = 0, 0
    for i, j in enumerate(a):
        if j:
            X+=V[i]
            Y+=C[i]
    ans = max(ans, X-Y)
print(ans)

Fixed submission:
from itertools import product as p

N = int(input())
*V, = map(int, input().split())
*C, = map(int, input().split())

ans = 0
for a in p(range(2), repeat=N):
    X, Y = 0, 0
    for i, j in enumerate(a):
        if j:
            X+=V[i]
            Y+=C[i]
    ans = max(ans, X-Y)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
K = int(input())
print("".join([i for i in S if i==S[K-1] else "*"]))

Fixed submission:
N = int(input())
S = input()
K = int(input())
print("".join([i if i==S[K-1] else "*" for i in S]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
l = [int(input()) for _ in range(N)]
dp = [0] * (N+1)
pos = [-1]*(N+1)
dp[0] = 1
MOD = 10**9+7

for i in  range(1, N+1):
    p = pos[l[i-1]]
    if i-p>1 and p!=-1:
        dp[i] += dp[p]
    pos[l[i-1]] = i
    dp[i] += dp[i-1]
    dp[i] %= MOD
    
print(dp[-1])

Fixed submission:
from collections import defaultdict

N = int(input())
l = [int(input()) for _ in range(N)]
dp = [0] * (N+1)
pos = defaultdict(lambda: -1)
dp[0] = 1
MOD = 10**9+7

for i in  range(1, N+1):
    p = pos[l[i-1]]
    if i-p>1 and p!=-1:
        dp[i] += dp[p]
    pos[l[i-1]] = i
    dp[i] += dp[i-1]
    dp[i] %= MOD
    
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
rank=0
for i in range(1,max(a,b)+1):
  	if a%i==0 and b%i==0:
      rank+=1
    if rank==c:
      print(i)
      break

Fixed submission:
a,b,c=map(int,input().split())
l=[]
for i in range(1,max(a,b)+1):
  if a%i==0 and b%i==0:
    l.append(i)
print(l[-c])
Buggy python submission (verdict: Runtime Error):
l = []
ans = 0

for s in input():
    if s == "0":
        if l and l[-1] == "1":
            l.pop()
            ans += 2
        else:
            l.append(s)
    else:
        if l and l[-1] == "0":
            l.pop()
            ans += 2
        else:
            l.append(i)

print(ans)

Fixed submission:
a,b=0,0
for i in input():
  if i=="1":a+=1
  else:b+=1
print(2*min(a,b))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*A, = map(int, input().split())

d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

dp = [0] * (N+1)
digit = [0] * (N+1)

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0 or 0<i-cost<minpos: continue
        a = dp[i]
        b = dp[i-cost] + n * (10**(digit[i-cost]))
        if a<b:
            dp[i] = b
            digit[i] = digit[i-cost] + 1

print(dp[N])

Fixed submission:
from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*A, = map(int, input().split())

dp = [""] * (N+1)
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

c = [(i, d[i]) for i in A]
c.sort(key=lambda x:(-x[1], -x[0]))
minpos = min(c, key=lambda x:x[1])[1]

dp[0] = ""
dp[1] = ""

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0: continue
        if 0<i-cost<minpos: continue
        a = int(dp[i]) if dp[i] else 0
        b = int(str(n) + dp[i-cost])
        if a<b:
            dp[i] = str(n) + dp[i-cost]

print(dp[N])

Fixed submission:
from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)
Buggy python submission (verdict: Time Limit Exceeded):
def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))


Fixed submission:
def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))