Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
box = [list(map(int, input().split())) for i in range(n)]

li = sorted(box, key = lambda x: sum(x), reverse = True)

taka = []
aoki = []

for i in range(len(li)):
    taka.append(li[0][0])
    del li[0]
    if li == []:
        print(sum(taka) - sum(aoki))
        quit()
    aoki.append(li[0][1])
    del li[0]

print(sum(taka) - sum(aoki))

Fixed submission:
n = int(input())
box = [list(map(int, input().split())) for i in range(n)]

li = list(sorted(box, key=lambda x: sum(x), reverse = True))

taka = []
aoki = []

for i in range(len(li)):
    taka.append(li[0][0])
    del li[0]
    if li == []:
        print(sum(taka) - sum(aoki))
        quit()
    aoki.append(li[0][1])
    del li[0]
    if li ==[]:
        print(sum(taka) - sum(aoki))
        quit()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())) + [0]*(k+1))
dp = np.array([0] + [float("inf")] * (n+k+1))

for i in range(1, n):
    s = max(0, i-k)
    dp[i] = min(dp[s:i] + abs(h[i] - h[s:i]))

print(int(dp[n-1]))

Fixed submission:
import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
h = list(map(int, input().split())) + [0]*(k+1)
dp = [0] + [float("inf")] * (n+k+1)

for i in range(n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j], (dp[i] + abs(h[i+j] - h[i])))

print(dp[n-1])

Fixed submission:
import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
li = list(map(int, input().split())) + [0] * (k-1)

dp = [0] + [float("inf")] * (n + k -1)

for i in range(n-1):
    for k in range(1,k+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(li[i+k] - li[i]))

print(dp[n-1])

Fixed submission:
import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
li = list(map(int, input().split())) + [0] * k

dp = [0] + [float("inf")] * (n + k)

for i in range(n-1):
    for k in range(1,k+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(li[i+k] - li[i]))

print(dp[n-1])

Fixed submission:
import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
k, s = list(map(int, input().split()))
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1
print(count)

Fixed submission:
k, s = list(map(int, input().split()))
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0<= z <= k:
            count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
p = 1
start = ""
end = ""
query =[]
for i in range(q):
    a = list(map(str,input().split()))
    query.append(a)

for i in range(q):
    if int(query[i][0]) == 1:
        p = p * (-1)
    else:
        if int(query[i][1]) == 1:
            if p ==1:
                start = query[i][2] + start
            else:
                end = query[i][2] + end
        else:
            if p == 1:
                end = query[i][2] + end
            else:
                start = query[i][2] + start
if p == 1:
    ans = start + s + end[::-1]
else:
    ans = end + s[::-1] + start[::-1]
print(ans)

Fixed submission:
s = input()
q = int(input())
p = 1
start = ""
end = ""
query =[]
for i in range(q):
    a = list(map(str,input().split()))
    query.append(a)

for i in range(q):
    if int(query[i][0]) == 1:
        p = p * (-1)
    else:
        if int(query[i][1]) == 1:
            if p ==1:
                start = query[i][2] + start
            else:
                end = query[i][2] + end
        else:
            if p == 1:
                end = query[i][2] + end
            else:
                start = query[i][2] + start
if p == 1:
    ans = start + s + end[::-1]
else:
    ans = end + s[::-1] + start[::-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n , k =list(map(int,input().split()))
p = list(map(int,input().split()))
maxval = 0
for i in range(n-k+1):
    if sum(p[i:i+k]) > maxval:
        maxval = sum(p[i:i+k])
        idx = i
print((maxval+k)/2)

Fixed submission:
n , k =list(map(int,input().split()))
p = list(map(int,input().split()))
maxval = sum(p[0:k])
now = sum(p[0:k]) + p[-1] - p[k-1]
for i in range(n-k+1):
    now = now - p[i-1] + p[i+k-1]
    if  now > maxval:
        maxval = now

print((maxval+k)/2)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int,input().split()))
cnt = 0
for i in range(n):
    judge = 0
    for j in range(i):
        if p[i] > p[j]:
            judge=1
            break
        else:
            pass
    if judge == 0:    
        cnt += 1
print(cnt)

Fixed submission:
n = int(input())
p = list(map(int,input().split()))
cnt = 0
min = p[0]
for i in range(n):
    if p[i] <= min:
        min = p[i]
        cnt += 1
    else:
        pass
print(cnt)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
n = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
list = make_divisors(n)
root = int(n**0.5)+1
for i in range(len(list)-1):
    if (list[i] <= root and list[i+1] >root):
        a= list[i]
if n == 1:
    a=1
b = n //a
print(a+b-2)

Fixed submission:
# coding: utf-8
# Your code here!
n = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
list = make_divisors(n)
root = n**0.5
for i in range(len(list)-1):
    if (list[i] <= root and list[i+1] >root):
        a = list[i]
b = n //a
print(a+b-2)

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
n = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
list = make_divisors(n)
root = int(n**0.5)+1
for i in range(len(list)):
    if (list[i] <= root and list[i+1] >root):
        a= list[i]
b = n //a
print(a+b-2)

Fixed submission:
# coding: utf-8
# Your code here!
n = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
list = make_divisors(n)
root = n**0.5
for i in range(len(list)-1):
    if (list[i] <= root and list[i+1] >root):
        a = list[i]
b = n //a
print(a+b-2)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=np.amax(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)

Fixed submission:
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=max(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=np.amax(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)

Fixed submission:
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=max(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a=list(map(int,input().split()))
j = 1
ans = list()
while j <= n:
    ans.append(a.index(j)+1)
    j = j+1
print(' '.join(map(str, ans)))


Fixed submission:
n = int(input())
a=list(map(int,input().split()))
j = 1
ans = [0] * n
while j <= n:
    ans[a[j-1]-1] =  j
    j = j+1
print(' '.join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
import numpy as np
a = list(map(int,input().split()))
bb = np.ones((a[2],a[3]))
bc = np.zeros((a[2],a[1]-a[3]))
cb = np.zeros((a[0]-a[2],a[3]))
cc = np.ones((a[0]-a[2],a[1]-a[3]))
ans = np.r_[np.c_[bb,bc],np.c_[cb,cc]]
print(ans)

Fixed submission:
h, w, a, b=list(map(int,input().split()))
for i in range(b):
    print("1"*a + "0"*(w-a))
for i in range(h-b):
    print("0"*a + "1"*(w-a))
Buggy python submission (verdict: Runtime Error):
    n = int(input())
    b = list(map(int,input().split()))
    a = [0] *n
    for i in range(0,n-2):
        a[i+1] = min([b[i],b[i+1]])
    a[0] =a[1]
    a[n-1] = b[n-2]
    print(sum(a))

Fixed submission:
n = int(input())
b = list(map(int,input().split()))
a = [0] *n
for i in range(0,n-2):
    a[i+1] = min([b[i],b[i+1]])
    # if a[n-1-i] <= b[n-2-i]:
    #     a[n-2-i] = b[n-2-i]
    # else:
    #     a[n-1-i] = b[n-2-i]
    #     a[n-2-i] = b[n-2-i]
a[0] =b[0]
a[n-1] = b[n-2]
print(sum(a))
Buggy python submission (verdict: Runtime Error):
n = int(input())
h= list(map(int,input().split()))
a = []
cnt = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        cnt = cnt + 1
    else:
        cnt = 0
    a.append(cnt)
print(max(a))

Fixed submission:
n = int(input())
h= list(map(int,input().split()))
a = [0]
cnt = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        cnt = cnt + 1
    else:
        cnt = 0
    a.append(cnt)
print(max(a))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
cnt = 0
for i in range(n):
   cnt += i
print(cnt)

Fixed submission:
n = int(input())
ans = n * (n-1) //2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
cnt = 0
for i in range(n):
   cnt += i
print(cnt)

Fixed submission:
n = int(input())
ans = n * (n-1) //2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
Q = int(input())
t_count = 0

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    t_count += 1
  else:
    if t_count%2 == 1:
      S.reverse()
      t_count = 0
    F, C = int(list_[1]), list_[2]
    if F == 1:
      S.insert(0,C)
    else:
      S.append(C)
if t_count%2 == 1:
      S.reverse()
ans = ''.join(S)
print(ans)

Fixed submission:
S = list(input())
Q = int(input())
t_count = 0
before = []
after = []

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    t_count += 1
  else:
    F, C = int(list_[1]), list_[2]
    if F == 1:
      if t_count%2 == 0:
        before.append(C)
      else:
        after.append(C)
    else:
      if t_count%2 == 0:
        after.append(C)
      else:
        before.append(C)
before.reverse()
S.extend(after)
before.extend(S)
if t_count%2 == 1:
  before.reverse() 
ans = ''.join(before)
print(ans)

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

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    S.reverse()
  else:
    F, C = int(list_[1]), list_[2]
    if F == 1:
      S.insert(0, C)
    else:
      S.append(C)
ans = ''.join(S)
print(ans)

Fixed submission:
S = list(input())
Q = int(input())
t_count = 0
before = []
after = []

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    t_count += 1
  else:
    F, C = int(list_[1]), list_[2]
    if F == 1:
      if t_count%2 == 0:
        before.append(C)
      else:
        after.append(C)
    else:
      if t_count%2 == 0:
        after.append(C)
      else:
        before.append(C)
before.reverse()
S.extend(after)
before.extend(S)
if t_count%2 == 1:
  before.reverse() 
ans = ''.join(before)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

N = int(input())
dic = {}
for i in range(N):
  s = str(input())
  if dic.get(s):
    dic[s] += 1
  else:
    dic[s] = 1

max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list.sort()
s_n = '\n'.join(max_k_list)
print(s_n)

Fixed submission:
N = int(input())
dic = {}
nmax = 1
for i in range(N):
  s = str(input())
  if s in dic:
    dic[s] += 1
    #毎回dic更新する度に最大値も更新
    nmax = max(dic[s], nmax)
  else:
    dic[s] = 1
slist = []
for k in dic:
  if dic[k] == nmax:
    slist.append(k)
for s in sorted(slist):
  print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_list = list(map(int,input().split()))

sw = 0
for i in range(len(A_list)):
  for j in range(i+1, len(A_list)):
    if A_list[i] == A_list[j]:
      sw = 1
      break
if sw == 1:
  print('NO')
else:
  print('YES')

Fixed submission:
N = int(input())
A_list = list(map(int,input().split()))
A_list.sort()
sw = 0
for i in range(len(A_list)-1):
  if A_list[i] == A_list[i+1]:
    sw = 1
    break
if sw == 0:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
import numpy as np
H, N = map(int, input().split())
dp = np.zeros((N, H+1))
skills = []
for _ in range(N):
  a, b = map(int, input().split())
  skills.append([a,b])

for i in range(1,H+1):
  for j in range(N):
    if i - skills[j][0] >0:
      dp[j][i] = min(dp[0][i-skills[j][0]], dp[1][i-skills[j][0]], dp[2][i-skills[j][0]])+skills[j][1]
    else:
      dp[j][i] = skills[j][1]

print(int(min(dp.T[-1])))

Fixed submission:
import numpy as np
H, N = map(int, input().split())
dp = np.zeros((N, H+1))
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, _ in ab)
dp = [0]*(H+max_a)
for i in range(1,H+1):
  dp[i] = min(dp[i-a]+b for a,b in ab)
#print(ab)
print(dp[H])
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N%2 != 0:
  answer = 0
else:
  answer_2 = 0
  n = 1
  while (N/2)//(2**n) != 0:
    answer_2 += int((N/2)//(2**n))
    n += 1 
  answer_5 = 0
  m = 1
  while (N/2)//(5**m) != 0:
    answer_5 += int((N/2)//(5**m))
    m += 1 
answer = min(answer_2, answer_5)
print(answer)

Fixed submission:
import math
N = int(input())

if N%2 != 0:
  answer = 0
else:
  answer = 0
  m = 1
  while math.floor(N)//(2*5**m) > 0:
    answer += math.floor(N//(2*5**m))
    m += 1 
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) 
N, M = map(int, input().split())
a_list = []
dp = [0]*(N+1)
for _ in range(M):
  a = int(input())
  a_list.append(a)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])

Fixed submission:
N, M = map(int, input().split())
a_list = set([int(input()) for i in range(M)])
dp = [0]*(N+1)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
a_list = []
dp = [0]*(N+1)
for _ in range(M):
  a = int(input())
  a_list.append(a)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])

Fixed submission:
N, M = map(int, input().split())
a_list = set([int(input()) for i in range(M)])
dp = [0]*(N+1)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
name_list = []
score_list = []
score_list_new = []
for i in range(N):
  name, score =  map(str,input().split())
  name_list.append(name)
  score_list.append(int(score))
index_name = np.argsort(name_list)
for i in range (len(score_list)):
  score_list_new.append(score_list[index_name[i]])
for i in range(len(index_name)):
  for j in range(i,len(index_name)):
  	if (name_list[i] == name_index[j]) and (score_list_new[i] < score_list_new[j]):
      index_name[i], index_name[j] = index_name[j], index_name[i]
    else:
      None  
for i in range(len(index_name)):
  print(index_name[i])

Fixed submission:
import numpy as np
N = int(input())
restaurants_list = []
for i in range(N):
  name,score = map(str,input().split())
  score = int(score)
  restaurants_list.append([name,score,i+1])
restaurants_list.sort(key = lambda x:x[1],reverse=True) 
restaurants_list.sort(key = lambda x:x[0]) 
for i in range(N):
  print(restaurants_list[i][2])
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
V_list = list(map(int,input().split()))
min_ = min(N,K)
total = []
#get
for a in range(min_):
  for b in range(min_-a):
    score_get = V_list[:a]+V_list[N-b:]
    score_get.sort()
    if len(score_get) == 0:
      score_get.append(0)
    for i in range(min(K-(a+b)+1,len(score_get))):
      if score_get[i]<0:
        new_score = score_get[:i]+score_get[i+1:]
      else:
        break
      total_score = sum(new_score)
      total.append(total_score)
print(max(total))
      

Fixed submission:
N,K = map(int,input().split())
V_list = list(map(int,input().split()))
min_ = min(N,K)
total = [0]
#get
for a in range(min_+1):
  for b in range(min_-a+1):
    score_get = V_list[:a]+V_list[N-b:]
    score_get.sort()
    score = sum(score_get)
    for i in range(min(K-(a+b),len(score_get))):
      if score_get[i]<0:
        score -= score_get[i]
      else:
        break
    total.append(score)
print(max(total))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N,W+1))
for i in range(N):
  w, v = map(int, input().split())
  for j in range(1,W+1):
    if j-w >= 0:
      dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(int(dp[-1][-1]))

Fixed submission:
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n, w = map(int, input().split())
dp = np.zeros((n+1, w+1))

for i in range(1,n+1):
  wn, vn = map(int, input().split())
  for j in range(1, w+1):
    if j-wn >= 0:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-wn]+vn)
    else:
      dp[i][j] = dp[i-1][j]
print(int(dp[-1][-1]))

Fixed submission:
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))
Buggy python submission (verdict: Runtime Error):
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))

Fixed submission:
import numpy as np
n, w = map(int, input().split())
v_max = 1000
num_v = v_max*n
INF = 10**9+1
dp = np.full(num_v+1, INF, dtype=int)
dp[0] = 0
for i in range(1,n+1):
  wn, vn = map(int, input().split())
  dp[vn:] = np.minimum(dp[vn:], dp[:-vn]+wn)
for i in range(len(dp)-1, -1, -1):
  if dp[i] <= w:
    print(i)
    break
Buggy python submission (verdict: Time Limit Exceeded):
### bfs ###
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
que = []
for _ in range(N-1):
    a, b, c = map(int, input( ).split( ))
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
Q, K = map(int, input().split())
K -= 1
dis[K] = 0
que.append(K) #dfs
while que:
    p = que.pop(0)
    for i in range(len(G[p])):
        n_p, d = G[p][i]
        if dis[n_p] != -1:
            continue
        que.append(n_p)
        dis[n_p] = dis[p] + d

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = dis[x]+dis[y]
    print(ans)
   
    
 

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

N = int(input())
tree = [[] for _ in range(N)]
cost_from_k = [0]*N

def calcurate_cost(fr, to, cost):
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to, n_cost in tree[to]:
    if n_to == fr:
      continue
    if K != n_to:
      calcurate_cost(to, n_to, n_cost)
      
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append((b,c))
  tree[b].append((a,c))

  
Q, K = map(int, input().split())
K -= 1
calcurate_cost(K, K, 0)

for j in range(Q):
  x, y = map(int, input().split())
  print(cost_from_k[x-1]+cost_from_k[y-1])

Buggy python submission (verdict: Time Limit Exceeded):
## bfs ##
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
que = []
for _ in range(N-1):
    a, b, c = map(int, input( ).split( ))
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
Q, K = map(int, input().split())
K -= 1
dis[K] = 0
que.append(K) 
while que:
    p = que.pop(0)
    for i in range(len(G[p])):
        n_p, d = G[p][i]
        if dis[n_p] != -1:
            continue
        que.append(n_p)
        dis[n_p] = dis[p] + d

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = dis[x]+dis[y]
    print(ans)
   
    

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

N = int(input())
tree = [[] for _ in range(N)]
cost_from_k = [0]*N

def calcurate_cost(fr, to, cost):
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to, n_cost in tree[to]:
    if n_to == fr:
      continue
    if K != n_to:
      calcurate_cost(to, n_to, n_cost)
      
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append((b,c))
  tree[b].append((a,c))

  
Q, K = map(int, input().split())
K -= 1
calcurate_cost(K, K, 0)

for j in range(Q):
  x, y = map(int, input().split())
  print(cost_from_k[x-1]+cost_from_k[y-1])