Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
*S, = map(int, input().split())
*T, = map(int, input().split())

MOD = 10**9 + 7
P = []
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            P.append((i, j))
P.sort(key=lambda x: (x[0], -x[1]))

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

s = 0
for p, q in P:
    v = get(q+1) + 1
    add(q+2, v); s += v
print((s + 1) % MOD)

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

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

MOD = 10**9 + 7
s = 0
rM = range(M-1, -1, -1)
for i in range(N):
    si = S[i]
    for j in rM:
        if si == T[j]:
            v = get(j+1) + 1
            add(j+2, v); s += v
print((s + 1) % MOD)

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

MOD = 10**9 + 7
P = []
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            P.append((i, j))
P.sort(key=lambda x: (x[0], -x[1]))

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

s = 0
for p, q in P:
    v = get(q+1) + 1
    add(q+2, v); s += v
print((s + 1) % MOD)

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

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

MOD = 10**9 + 7
s = 0
rM = range(M-1, -1, -1)
for i in range(N):
    si = S[i]
    for j in rM:
        if si == T[j]:
            v = get(j+1) + 1
            add(j+2, v); s += v
print((s + 1) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
def solve(N, ga, gb, sa, sb, ba, bb):
    V = [gb, sb, bb]
    W = [ga, sa, ba]
    dp = [i for i in range(N+1)]
    for v, w in zip(V, W):
        if v <= w:
            continue
        for k in range(w, N+1):
            dp[k] = max(dp[k], dp[k-w] + v)
    return max(dp)

A = solve(N, ga, gb, sa, sb, ba, bb)
B = solve(A, gb, ga, sb, sa, bb, ba)
print(B)

Fixed submission:
N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
def solve(N, P):
    V = []; W = []
    for w, v in P:
        if w < v:
            V.append(v); W.append(w)
    if len(V) == 1:
        v = V[0]; w = W[0]
        k = N // w
        return N - k*w + k*v
    if len(V) == 2:
        w1, w2 = W
        M = w1 * w2
        dp = [i for i in range(M+1)]
        for v, w in zip(V, W):
            if v <= w:
                continue
            for k in range(w, M+1):
                dp[k] = max(dp[k], dp[k-w] + v)
        for i in range(M):
            dp[i+1] = max(dp[i+1], dp[i])
        ans = 0
        for i in range(M):
            k, r = divmod(N, (i+1))
            ans = max(ans, dp[i+1] * k + dp[r])
        return ans
    dp = [i for i in range(N+1)]
    for v, w in zip(V, W):
        if v <= w:
            continue
        for k in range(w, N+1):
            dp[k] = max(dp[k], dp[k-w] + v)
    return max(dp)

A = solve(N, [[ga, gb], [sa, sb], [ba, bb]])
B = solve(A, [[gb, ga], [sb, sa], [bb, ba]])
print(B)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
*S, = map(int, input().split())

ans = 0
for a in range(1, N):
    d = 1
    while d*d <= N-1-a:
        if (N-1-a) % d == 0:
            if a > d and (a % d > 0 or N-1-a < a):
                k = (N-1-a) // d
                s = 0
                for i in range(k):
                    s += S[i*d+d] + S[i*d+a]
                ans = max(ans, s)
            e = (N-1-a) // d
            if a > e and (a % e > 0 or N-1-a < a):
                k = (N-1-a) // e
                s = 0
                for i in range(k):
                    s += S[i*e+e] + S[i*e+a]
                ans = max(ans, s)
        d += 1
print(ans)

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

ans = 0
for d in range(1, N):
    r = k = 0
    while k*d <= N-1:
        a = N-1-k*d
        if a <= d or (a <= k*d and a % d == 0):
            break
        r += S[N-1-k*d] + S[k*d]
        k += 1
        ans = max(ans, r)
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
if A >= 13:
    print(B)
elif A >= 6:
    print(B//2)
else:
    print(0)

Fixed submission:
r, D, x = map(int, input().split())
for i in range(10):
    x = r*x - D
    print(x)
Buggy python submission (verdict: Runtime Error):
M, K = map(int, input().split())
if 2**M <= K:
    print(-1)
    exit(0)
if M == 1:
    if K == 1:
        print(-1)
    else:
        print("0 0 1 1")
else:
    *R, = [i for i in range(2**M) if i != K]
    print(K, *R, K, *reversed(R))

Fixed submission:
M, K = map(int, input().split())
if 2**M <= K:
    print(-1)
    exit(0)
if M == 1:
    if K == 1:
        print(-1)
    else:
        print("0 0 1 1")
else:
    R = [i for i in range(2**M) if i != K]
    *S, = reversed(R)
    ans = [K] + R + [K] + S
    print(*ans)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        p[py] = px
    else:
        p[px] = py
*p, = range(N)

for i in range(M):
    x, y, z = map(int, input().split())
    unite(x-1, y-1)
ans = 0
for i in range(N):
    if root(i) == i:
        ans += 1
print(ans)

Fixed submission:
M, K = map(int, input().split())
if 2**M <= K:
    print(-1)
    exit(0)
if M == 1:
    if K == 1:
        print(-1)
    else:
        print("0 0 1 1")
else:
    R = [i for i in range(2**M) if i != K]
    *S, = reversed(R)
    ans = [K] + R + [K] + S
    print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N+1):
    if N < R*r:
        break
    for g in range(N+1):
        if N < R*r + G*g:
            break
        if (N - R*r - G*g) % B == 0:
            ans += 1
print(ans)

Fixed submission:
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N+1):
    for g in range(N+1):
        s = N - R*r - G*g
        if s >= 0 and s % B == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N+1):
    for g in range(N+1):
        s = N - R*r - G*g
        if s >= 0 and s % B == 0:
            ans += 1
print(ans)

Fixed submission:
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N+1):
    for g in range(N+1):
        s = N - R*r - G*g
        if s >= 0 and s % B == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N = int(readline())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

memo = [-1]*(d+2)
memo[0] = 0
memo[1] = 1
memo[2] = 0
def dfs(d):
    if memo[d] != -1:
        return memo[d]
    if dfs(d-1) == 0 or dfs(d-2) == 0:
        memo[d] = 1
        return 1
    memo[d] = 0
    return 0
print("First" if dfs(d+1) else "Second")

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N = int(readline())
if N == 1:
    print("First")
    exit(0)
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

memo = [-1]*(d+2)
memo[0] = 0
memo[1] = 1
memo[2] = 0
for i in range(3, d+2):
    if memo[i-1] == 0 or memo[i-2] == 0:
        memo[i] = 1
    else:
        memo[i] = 0
print("First" if memo[d+1] else "Second")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

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

ans = -10**18
for p in product([0, 1], repeat=N):
    res = 0
    for i, e in enumerate(p):
        if e:
            res += V[i] - C[i]
    ans = max(ans, res)
print(ans)

Fixed submission:
from itertools import product

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

ans = -10**18
for p in product([0, 1], repeat=N):
    res = 0
    for i, e in enumerate(p):
        if e:
            res += V[i] - C[i]
    ans = max(ans, res)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

Fixed submission:
N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= right:
        v = S[cur-1]+c
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
while len(ans) < K:
    ans.append(left)
print(*ans[:K], sep='\n')

Fixed submission:
X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= left:
        v = S[cur-1]+c
        if v == left and len(ans) >= K:
            break
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
print(*ans[:K], sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= left:
        v = S[cur-1]+c
        if v == left and len(ans) >= K:
            break
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
print(*ans[:K], sep='\n')

Fixed submission:
X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= left:
        v = S[cur-1]+c
        if v == left and len(ans) >= K:
            break
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
print(*ans[:K], sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int, input().split())
*S, = map(int, input().split())

MOD = 10**9 + 7

fact = [1]*(X+1)
rfact = [1]*(X+1)
for i in range(X):
    fact[i+1] = r = fact[i] * (i+1) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

S.sort()
memo = {}
def dfs(i, k):
    key = (i, k)
    if key in memo:
        return memo[key]
    if i == N:
        return k == X
    r = dfs(i+1, k) * i % MOD
    if k <= S[i]:
        for j in range(k, X+1, S[i]):
            r = (r + dfs(i+1, j)) % MOD
    memo[key] = r
    return r
print(sum(x*dfs(0, x)%MOD for x in range(S[0])) % MOD)

Fixed submission:
N, X = map(int, input().split())
*V, = map(int, input().split())

MOD = 10**9 + 7

fact = [1]*(X+1)
rfact = [1]*(X+1)
for i in range(X):
    fact[i+1] = r = fact[i] * (i+1) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

V.sort()

S = [0]*(X+1)
S[X] = 1
for i in range(N-1, -1, -1):
    T = [0]*(X+1)
    for k in range(X+1):
        S[k] %= MOD
        T[k] += S[k] * i % MOD
        T[k % V[i]] += S[k]
    S = T
print(sum(k*S[k] % MOD for k in range(V[0])) % MOD)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N, K = map(int, input().split())
T = defaultdict(list)
for i in range(N):
    t, d = map(int, input().split())
    T[t].append(d)
S = []
U = []
for k, v in T.items():
    v.sort(reverse=1)
    U.append((v[0], k))
    for w in v[1:]:
        S.append((w, k))
S.sort(reverse=1)
U.sort(reverse=1)
D = defaultdict(int)
cnt = 0
D[U[0][1]] += 1
t = 1
cnt += 1
res = U[0][0]
S = S[:K-1]
for w, k in S:
    D[k] += 1
    if D[k] == 1:
        t += 1
    cnt += 1
    res += w
ans = 0
for v, k in U[1:]:
    D[k] += 1
    if D[k] == 1:
        t += 1
    cnt += 1
    res += v
    while cnt > K:
        cnt -= 1
        w, l = S.pop()
        D[l] -= 1
        if D[l] == 0:
            t -= 1
        res -= w
    print(t, res, cnt)
    ans = max(ans, t*t + res)
print(ans)

Fixed submission:
from collections import defaultdict
N, K = map(int, input().split())
T = defaultdict(list)
for i in range(N):
    t, d = map(int, input().split())
    T[t].append(d)
S = []; U = []
for k, v in T.items():
    v.sort(reverse=1)
    U.append((v[0], k))
    for w in v[1:]:
        S.append((w, k))
S.sort(reverse=1)
U.sort(reverse=1)
D = defaultdict(int)
t = cnt = 0
res = 0
for w, k in S:
    D[k] += 1
    if D[k] == 1:
        t += 1
    cnt += 1
    res += w
ans = 0
can = 1
for v, k in U:
    D[k] += 1
    if D[k] == 1:
        t += 1
    cnt += 1
    res += v
    while cnt > K:
        if not S:
            can = 0
            break
        cnt -= 1
        w, l = S.pop()
        D[l] -= 1
        if D[l] == 0:
            t -= 1
        res -= w
    if not can:
        break
    ans = max(ans, t*t + res)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*N
for i in range(1, N):
    v = 10**18
    for k in range(min(K, i)):
        v = min(v, dp[i-k-1] + abs(A[i] - A[i-k-1]))
    dp[i] = v
print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*N
for i in range(1, N):
    v = 10**18
    for k in range(min(K, i)):
        v = min(v, dp[i-k-1] + abs(A[i] - A[i-k-1]))
    dp[i] = v
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(max(dp))

Fixed submission:
N, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
V = 10**5
INF = 10**18
dp = [INF]*(V+1)

dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(V, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j], dp[j-v] + w)
for i in range(V, -1, -1):
    if dp[i] < INF:
        print(i)
        break

Fixed submission:
N, W = map(int, input().split())
V = 10**5
INF = 10**18
dp = [INF]*(V+1)

dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(V, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j], dp[j-v] + w)
for i in range(V, -1, -1):
    if dp[i] < INF:
        print(i)
        break
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1)) if t else  (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(T[0])

Fixed submission:
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(dp[N][0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

N = int(input())
*A, = map(int, input().split())
memo = [[-1]*(N+1) for i in range(N+1)]
for i in range(N+1):
    memo[i][i] = 0
def dfs(p, q, t):
    if memo[p][q] != -1:
        return memo[p][q]
    if t:
        r = min(dfs(p+1, q, 0) - A[p], dfs(p, q-1, 0) - A[q-1])
    else:
        r = max(dfs(p+1, q, 1) + A[p], dfs(p, q-1, 1) + A[q-1])
    memo[p][q] = r
    return r

print(dfs(0, N, 0))

Fixed submission:
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(dp[N][0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    yield -INF
    while L < R:
        if R & 1:
            R -= 1
            yield data[R-1]

        if L & 1:
            yield data[L-1]
            L += 1
        L >>= 1; R >>= 1

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
def solve():
    update(0, 0)
    yield 0
    for i in I:
        v = max(query(0, i+1)) + A[i]
        yield v
        update(i+1, v)
print(max(solve()))

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

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
ans = 0
update(0, 0)
for i in I:
    v = query(0, i+1) + A[i]
    ans = max(ans, v)
    update(i+1, v)
print(ans)

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

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


*I, = range(N)
I.sort(key=lambda x: (H[x], x))
def solve():
    update(0, 0)
    yield 0
    for i in I:
        v = query(0, i+1) + A[i]
        yield v
        update(i+1, v)
print(max(solve()))

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

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
ans = 0
update(0, 0)
for i in I:
    v = query(0, i+1) + A[i]
    ans = max(ans, v)
    update(i+1, v)
print(ans)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
K = input()
N = len(K)
D = int(input())
S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[d+v-D][1] += w0
        T[d+c-D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[d+v-D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)

Fixed submission:
MOD = 10**9 + 7
K = input()
N = len(K)
D = int(input())

S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[(d+v)%D][1] += w0
        T[(d+c)%D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[(d+v)%D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)