Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit("10**7")

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit("10**7")

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
  return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))

Buggy python submission (verdict: Runtime Error):
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
  return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = map(int, input().split())
TD = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True, key=itemgetter(1))
L = [[] for _ in range(n+1)]
P = []
a = 0
cnt = 0
F = [-float("inf")]*(n+1)
for t, d in TD[:k]:
  L[t].append(d)
  if len(L[t]) == 1:
    a += 1
  cnt += d
F[a] = cnt
for i in range(1, n+1):
  while len(L[i]) > 1:
    heapq.heappush(P, L[i].pop())
now = k
for i in range(a, n):
  while now < n and L[TD[now][0]]:
    now += 1
  if now == n:
    break
  t, d = TD[now]
  L[t].append(d)
  F[i+1] = F[i] - heapq.heappop(P) + d
ans = 0
for i in range(a, n+1):
  ans = max(ans, F[i] + i*i)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq
n, k = map(int, input().split())
TD = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True, key=itemgetter(1))
L = [[] for _ in range(n+1)]
P = []
a = 0
cnt = 0
F = [-float("inf")]*(n+1)
for t, d in TD[:k]:
  L[t].append(d)
  if len(L[t]) == 1:
    a += 1
  cnt += d
F[a] = cnt
for i in range(1, n+1):
  while len(L[i]) > 1:
    heapq.heappush(P, L[i].pop())
now = k
for i in range(a, n):
  if len(P) == 0:
    break
  while now < n and L[TD[now][0]]:
    now += 1
  if now == n:
    break
  t, d = TD[now]
  L[t].append(d)
  F[i+1] = F[i] - heapq.heappop(P) + d
ans = 0
for i in range(a, n+1):
  ans = max(ans, F[i] + i*i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
  n, W = map(int, input().split())
  dp = [0]*(W+1)
  for _ in range(n):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
      dp[j] = max(dp[j-w] + v, dp[j])
  print(dp[W])
  
if __name__ == "__main__":
  main()

Fixed submission:
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
  w, v = map(int, input().split())
  for j in range(W, w-1, -1):
    dp[j] = max(dp[j-w] + v, dp[j])
print(dp[W])

Fixed submission:
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])

Fixed submission:
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])
Buggy python submission (verdict: Runtime Error):
n, w = map(int, input().split())
l = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*(w+1) for _ in range(n+1) ]
for i in range(1, n+1):
  for j in range(w+1):
    if j < l[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-l[i-1][0]] + l[i-1][1], dp[i-1][j])
print(dp[n][w])


Fixed submission:
n, W = map(int, input().split())
wv = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [float("inf")]*(10**5+1) for _ in range(n+1) ]
dp[0][0] = 0
for i in range(n):
  w, v = wv[i]
  for j in range(10**5+1):
    if j < v:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
ans = 0
for j in range(10**5+1):
  if dp[n][j] <= W:
    ans = j
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
P = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
  for j in range(n+1):
    if j==0:
      dp[i+1][j] = dp[i][j]*(1-P[i])
    else:
      dp[i+1][j] = dp[i][j-1]*P[i] + dp[i][j]*(1-P[i])
print(sum(dp[n][1+n//2:]))

Fixed submission:
n = int(input())
P = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
  for j in range(n+1):
    if j==0:
      dp[i+1][j] = dp[i][j]*(1-P[i])
    else:
      dp[i+1][j] = dp[i][j-1]*P[i] + dp[i][j]*(1-P[i])
print(sum(dp[n][1+n//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [0]*(k+1)
for i in range(k+1):
  for a in A:
    if i-a >= 0:
      dp[i] |= not dp[i-a]
result = dp[k]
if result:
  print("First")
else:
  print("Second")

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1]*(k+1)
def dfs(k):
  if dp[k] != -1:
    return dp[k]
  for a in A:
    if k-a >= 0 and dfs(k-a) == 0:
      dp[k] = 1
      return 1
  dp[k] = 0
  return 0
result = dfs(k)
if result:
  print("First")
else:
  print("Second")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [0]*(k+1)
for i in range(k+1):
  for a in A:
    if i-a >= 0:
      dp[i] |= ~dp[i-a]
result = dp[k]
if result:
  print("First")
else:
  print("Second")

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1]*(k+1)
def dfs(k):
  if dp[k] != -1:
    return dp[k]
  for a in A:
    if k-a >= 0 and dfs(k-a) == 0:
      dp[k] = 1
      return 1
  dp[k] = 0
  return 0
result = dfs(k)
if result:
  print("First")
else:
  print("Second")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [0] + list(accumulate(A))
  dp = [[0]*(n+1) for i in range(n+1)]
  for d in range(1, n+1):
    for i in range(n+1-d):
      dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
  ans = 2*dp[0][n] - L[n]
  print(ans)
if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[0]*(n+1) for i in range(n+1)]
for d in range(1, n+1):
  for i in range(n+1-d):
    dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
ans = 2*dp[0][n] - L[n]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[-1]*(n+1) for i in range(n+1)]
def dfs(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == j:
    dp[i][j] = 0
    return 0
  res = max(A[i] + L[j] - L[i+1] - dfs(i+1, j), A[j-1] + L[j-1] - L[i] - dfs(i, j-1))
  dp[i][j] = res
  return res
dfs(0, n)
ans = 2*dp[0][n] - L[n]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[0]*(n+1) for i in range(n+1)]
for d in range(1, n+1):
  for i in range(n+1-d):
    dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
ans = 2*dp[0][n] - L[n]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[-1]*(n+1) for i in range(n+1)]
def dfs(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == j:
    dp[i][j] = 0
    return 0
  res = max(A[i] + L[j] - L[i+1] - dfs(i+1, j), A[j-1] + L[j-1] - L[i] - dfs(i, j-1))
  dp[i][j] = res
  return res
dfs(0, n)
ans = 2*dp[0][n] - L[n]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[0]*(n+1) for i in range(n+1)]
for d in range(1, n+1):
  for i in range(n+1-d):
    dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
ans = 2*dp[0][n] - L[n]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for j in range(k+1):
    if j == 0:
      dp[i+1][j] = 1
    elif j <= a:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
    else:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a-1]
    dp[i+1][j] %= MOD
ans = dp[n][k]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for j in range(k+1):
    if j == 0:
      dp[i+1][j] = 1
    elif j <= a:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
    else:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a-1]
    dp[i+1][j] %= MOD
ans = dp[n][k]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
n = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
dp = [[0]*(1<<n) for _ in range(n+1)]
dp[0][(1<<n)-1] = 1
for i in range(n):
  for j in range(n):
    for k in range(1<<n):
      if A[i][j] and (k>>j & 1):
        dp[i+1][k^(1<<j)] += dp[i][k]
        dp[i+1][k^(1<<j)] %= mod
ans = dp[n][0]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

mod = 10**9+7
n = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
dp = [[-1]*(1<<n) for _ in range(n+1)]
def f(i, k):
  if i == n:
    return 1
  if dp[i][k] != -1:
    return dp[i][k]
  res = 0
  for j in range(n):
    if A[i][j] and ((k>>j)&1):
      res += f(i+1, k^(1<<j))
      res %= mod
  dp[i][k] = res
  return res
ans = f(0, (1<<n)-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)

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

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

mod = 10**9+7
n, k = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
def matmul(X, Y):
  Z = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        Z[i][j] += X[i][k] * Y[k][j]
        Z[i][j] %= mod
  return Z
  
def matpow(k):
  if k == 1:
    return A
  if k%2:
    return matmul(A, matpow(k-1))
  X = matpow(k//2)
  return matmul(X, X)

B = matpow(k)
ans = 0
for i in range(n):
  for j in range(n):
    ans += B[i][j]
    ans %= mod
print(ans)

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

mod = 10**9+7
n, k = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
def matmul(X, Y):
  Z = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        Z[i][j] += X[i][k] * Y[k][j]
        Z[i][j] %= mod
  return Z
  
def matpow(k):
  if k == 1:
    return A
  if k%2:
    return matmul(A, matpow(k-1))
  X = matpow(k//2)
  return matmul(X, X)

B = matpow(k)
ans = 0
for i in range(n):
  for j in range(n):
    ans += B[i][j]
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
MOD = 10**9+7
n = int(input())
S = input()
dp = [1]*n
for s in S:
  if s == "<":
    dp = list(accumulate(dp[::-1][:-1]))[::-1]
  else:
    dp = list(accumulate(dp[:-1]))
ans = dp[0]%MOD
print(ans)

Fixed submission:
MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
S = input()
def main():
  dp = [[0]*(n+1) for _ in range(n+1)]
  for j in range(n):
    dp[1][j] = 1
  for i, s in enumerate(S, 1):
    if s == "<":
      dp[i+1][n-(i+1)] = dp[i][n-i]
      for j in range(n-i-2, -1, -1):
        dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
        dp[i+1][j] %= MOD
    else:
      dp[i+1][0] = dp[i][0]
      for j in range(1, n-i):
        dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
        dp[i+1][j] %= MOD
  ans = dp[n][0]
  print(ans)
if __name__ == "__main__":
  main()


Fixed submission:
MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)

Fixed submission:
MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
k = m//n
ans = 0
for i in range(1, int(m**0.5)+1):
  if m%i == 0:
    if i <= k:
      if i <= k:
      ans = max(ans, i)
    if m//i <= k:
      ans = max(ans, m//i)
print(ans)

Fixed submission:
n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i == 0:
    print(i)
    break

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i == 0:
    print(i)
    break

Fixed submission:
n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i == 0:
    print(i)
    break