Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,q = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

class RangeAddQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.data = [0]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] += v
            if l&1:
                self.data[l-1] += v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = 0
        while i+1:
            if self.data[i]:
                res += self.data[i]
            # (i-1)//2
            i = ~-i//2
        return res

label = [-1]*n
cnt = [0]
def dfs(i):
    if label[i] != -1:
        return
    label[i] = cnt[0]
    cnt[0] += 1
    for to in G[i]:
        dfs(to)

dfs(0)

nG = [[] for i in range(n)]
for i in range(n):
    for j in G[i]:
        nG[label[i]].append(label[j])

pos = [0]*n
cnt = [0]
vis = [False]*n
def dfs2(v):
    if vis[v]:
        return
    vis[v] = True
    order = cnt[0]
    cnt[0] += 1
    for to in nG[v]:
        dfs2(to)
    pos[order] = cnt[0]

dfs2(0)

RAQ = RangeAddQuery(n)

ans = []
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    v = label[p]
    RAQ.update(v, pos[v], x)

ans = [0]*n
for i in range(n):
    v = label[i]
    b = RAQ.query(v)
    ans[i] = b

print(*ans)

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

n,q = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    G[b].append(a)


a = [0]*n
for i in range(q):
    p,x = map(int, input().split())
    p -= 1
    a[p] += x

# bfs
from collections import deque
q = deque()
q.append((0,0))
visited = [0]*n
ans = [0]*n
while q:
    cur, cost = q.popleft()
    if visited[cur]:
        continue
    visited[cur] = 1
    cost += a[cur]
    ans[cur] = cost
    for to in G[cur]:
        if not visited[to]:
            q.append((to, cost))

print(*ans)
Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush
n, m = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n):
    a,b = map(int, input().split())
    c = min(m-a, n)
    if c < 0:
        continue
    heappush(l[c], -b)
heap = []
ans = 0
for i in range(n)[::-1]:
    for b in l[i]:
        heappush(heap, b)
    if heap:
        b = heappop(heap)
        ans += -b
print(ans)

Fixed submission:
from heapq import heappop, heappush
n, m = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n):
    a,b = map(int, input().split())
    c = min(m-a, n-1)
    if c < 0:
        continue
    heappush(l[c], -b)
heap = []
ans = 0
for i in range(n)[::-1]:
    for b in l[i]:
        heappush(heap, b)
    if heap:
        b = heappop(heap)
        ans += -b
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from copy import copy
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
d = Counter(a)

#print(d)
for i in range(1, n):
    one = prev = a[0]
    two = cur = a[i]
    dd = copy(d)
    end = True
    for j in range(n-2):
        nxt = prev^cur
        if dd[nxt] >0:
            dd[nxt] -= 1
        else:
            end = False
            break
        prev = cur
        cur = nxt
    if end and prev^cur == one and dd[one] > 0 and cur^one == two and dd[two] > 0:
        print("Yes")
        exit()
print("No")

Fixed submission:
from collections import Counter
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
if (len(c) == 1 and c[0] == n) or (len(c) == 2 and c[0] == n//3 and c[max(c.keys())] == 2*n//3) or (len(c) == 3 and reduce(lambda x, y: x^y, c.keys()) == 0 and set(c.values()) == set([n//3])):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from collections import deque

mod = 10**9+7
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)

start = None
for i in range(n):
    if len(edges[i]) == 1:
        start = i
        break

ans = 1
kumi = [0]*n
q = deque()
q.append((start,-1, 1, 0, 0))
while q:
    now, par, par_cnt,par2,child_cnt = q.popleft()
    a = par_cnt
    a *= k - par2 - child_cnt
    a %= mod
    cnt = 0
    for to in edges[now]:
        if to != par:
            if cnt == 0:
                q.append((to, now, a, min(par2+1, 2), 0))
            else:
                q.append((to, now, 1, min(par2+1, 2), cnt))
            cnt += 1
    if cnt == 0:
        ans *= a
        ans %= mod
print(ans)


Fixed submission:
from collections import deque

mod = 10**9+7
n, k = map(int, input().split())
edges = [[] for i in range(n)]
if n == 1:
    print(k)
    exit()
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)

start = None
for i in range(n):
    if len(edges[i]) == 1:
        start = i
        break

ans = 1
kumi = [0]*n
q = deque()
q.append((start,-1, 1, 0, 0))
while q:
    now, par, par_cnt,par2,child_cnt = q.popleft()
    a = par_cnt
    a *= k - par2 - child_cnt
    a %= mod
    cnt = 0
    for to in edges[now]:
        if to != par:
            if cnt == 0:
                q.append((to, now, a, min(par2+1, 2), 0))
            else:
                q.append((to, now, 1, min(par2+1, 2), cnt))
            cnt += 1
    if cnt == 0:
        ans *= a
        ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
import math
input = sys.stdin.readline
N, K = map(int, input().split())

def combinations(n, r):
    return math.factorial(n) // math.factorial(n - r) // math.factorial(r)

for i in range(1, K+1):
    remain = N - K
    ans = combinations(remain + 1, i) % 1000000007
    ans = ans * combinations(K-1, i-1) % 1000000007
    print(ans % 1000000007 )

Fixed submission:
class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

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

p = PERM_COMB_MOD()

mod = 10**9+7
n, k = map(int, input().split())
# n個をr個に分ける
def h(n, r):
    if n == 0 and r == 0:
        return 1
    return p.comb(n-1, r-1)

for i in range(1, k+1):
    blue = h(k, i)
    red = h(n-k, i-1) + 2*h(n-k, i) + h(n-k, i+1)
    ans = blue*red
    ans %= mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
b = list(map(int, input().split()))
b.sort()
if n == 2:
    print(b[-1]-b[0])
    print(b[-1], b[0])
    exit()
# 同符号
if b[0] > 0 and b[-1] > 0:
    ans = sum(b) - 2*b[0]
    print(ans)
    print(b[1], b[0])
    left = b[1] - b[0]
    right = b[-1]
    for i in range(2, n-1):
        x = left
        y = b[i]
        print(x, y)
        left = x - y
    print(right, left)
elif b[0] < 0 and b[-1] < 0:
    ans = -sum(b) + 2*b[-1]
    print(ans)
    b = b[::-1]
    print(b[0], b[1])
    left = 0
    right = b[0] - b[1]
    for i in range(2, n):
        x = right
        y = b[i]
        print(x, y)
        right = x - y
# 異符号
else:
    ans = abs(sum(abs(i) for i in b))
    print(ans)
    # 正,負がそれぞれ一つ以上ある
    # まず、正 - 負をして正を作って、負に引く
    now = 1
    left = b[0]
    right = b[-1]
    # 二個目以上の負を全部消化
    while b[now] <= 0:
        x = right
        y = b[now]
        print(x, y)
        right = x - y
        now += 1
    for i in range(now, n-1):
        x = left
        y = b[i]
        print(x, y)
        left = x - y
    print(right, left)

Fixed submission:
n = int(input())
b = list(map(int, input().split()))
b.sort()
if n == 2:
    print(b[-1]-b[0])
    print(b[-1], b[0])
    exit()
if b[0] == 0 and b[-1] == 0:
    print(0)
    for i in range(n-1):
        print(0,0)
elif b[0] > 0 and b[-1] > 0:
    ans = sum(b) - 2*b[0]
    print(ans)
    print(b[1], b[0])
    left = b[1] - b[0]
    right = b[-1]
    for i in range(2, n-1):
        x = left
        y = b[i]
        print(x, y)
        left = x - y
    print(right, left)
elif b[0] < 0 and b[-1] < 0:
    ans = -sum(b) + 2*b[-1]
    print(ans)
    b = b[::-1]
    print(b[0], b[1])
    left = 0
    right = b[0] - b[1]
    for i in range(2, n):
        x = right
        y = b[i]
        print(x, y)
        right = x - y
else:
    ans = abs(sum(abs(i) for i in b))
    print(ans)
    now = 1
    left = b[0]
    right = b[-1]
    while b[now] < 0:
        x = right
        y = b[now]
        print(x, y)
        right = x - y
        now += 1
    for i in range(now, n-1):
        x = left
        y = b[i]
        print(x, y)
        left = x - y
    print(right, left)
Buggy python submission (verdict: Runtime Error):
from math import log2, floor
n, k = map(int, input().split())
a = 1/n
ans = 0
for i in range(1, n+1):
    if i >= k:
        ans += a
        continue
    j = int(log2(k/i)) + 1
    if i*2**(j-1) == k:
        j -= 1
    ans += a/2**j
print(ans)

Fixed submission:
from math import log2, floor
n, k = map(int, input().split())
a = 1/n
ans = 0
for i in range(1, n+1):
    if i >= k:
        ans += a
        continue
    j = int(log2(k/i)) + 1
    if i*2**(j-1) == k:
        j -= 1
    ans += a/2**j
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

minus = []
plus = []

for i in a:
    if i < 0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort()
minus.sort(reverse=True)

if len(plus)*len(minus) == 0:
    plus[133],minus[133]
    print(sum(plus)-sum(minus))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])

Fixed submission:
n = int(input())
a = list(map(int,input().split()))

minus = []
plus = []

for i in a:
    if i < 0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort()
minus.sort(reverse=True)

if len(plus)==0:
    if len(minus)%2==0:
        print(-sum(minus))
    else:
        print(-sum(minus)+2*minus[0])
    exit()

if len(minus)==0:
    print(sum(a))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

minus = []
plus = []

for i in a:
    elif i < 0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort()
minus.sort(reverse=True)

if len(plus)*len(minus) == 0:
    plus[133],minus[133]
    print(sum(plus)-sum(minus))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])

Fixed submission:
n = int(input())
a = list(map(int,input().split()))

minus = []
plus = []

for i in a:
    if i < 0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort()
minus.sort(reverse=True)

if len(plus)==0:
    if len(minus)%2==0:
        print(-sum(minus))
    else:
        print(-sum(minus)+2*minus[0])
    exit()

if len(minus)==0:
    print(sum(a))
    exit()

if len(minus) % 2==0:
    print(sum(plus) - sum(minus))
    exit()

if - minus[0] < plus[0]:
    print(sum(plus) - sum(minus) +2*minus[0])
else:
    print(sum(plus) - sum(minus) -2*plus[0])
Buggy python submission (verdict: Runtime Error):
import math as m
a, b = list(map(int, input().split()))
bin_b = bin(b)[2:]
bin_a = bin(a)[2:].zfill(len(bin_b))
ans = []
for i in range(int(m.log2(b))+1):
    cnt = b-a+1
    d = {-1:0,1:0}
    ai = bin_a[-(i+1)]
    if ai == "0":
        ai = -1
    else:
        ai = 1
    if i == 0:
        hoge = 0
        if ai == 1:
            hoge = (cnt+1)//2
        else:
            hoge = cnt//2
        if hoge%2:
            ans.append(1)
        else:
            ans.append(0)
        continue
    ai_1 = int(bin_a[-i:],2) if i >0 else 0
    start = 2**i - ai_1
    if start >= cnt:
        d[ai] += cnt
        cnt = 0
    else:
        d[ai] += start
        cnt -= start
    ai *= -1
    hoge = cnt//(2**i)
    fuga = cnt % (2**i)
    if hoge%2:
        ai *= -1
    d[ai] += fuga
    if d[1]%2:
        ans.append(1)
    else:
        ans.append(0)
e = int("".join(map(str,ans[::-1])), 2)
print(e)

Fixed submission:
a, b = list(map(int, input().split()))
bin_b = bin(b)[2:]
bin_a = bin(a)[2:].zfill(len(bin_b))
ans = []
for i in range(len(bin_b)):
    cnt = b-a+1
    d = {-1:0,1:0}
    ai = bin_a[-(i+1)]
    if ai == "0":
        ai = -1
    else:
        ai = 1
    if i == 0:
        hoge = 0
        if ai == 1:
            hoge = (cnt+1)//2
        else:
            hoge = cnt//2
        if hoge%2:
            ans.append(1)
        else:
            ans.append(0)
        continue
    ai_1 = int(bin_a[-i:],2) if i >0 else 0
    start = 2**i - ai_1
    if start >= cnt:
        d[ai] += cnt
        cnt = 0
    else:
        d[ai] += start
        cnt -= start
    ai *= -1
    hoge = cnt//(2**i)
    fuga = cnt % (2**i)
    if hoge%2:
        ai *= -1
    d[ai] += fuga
    if d[1]%2:
        ans.append(1)
    else:
        ans.append(0)
e = int("".join(map(str,ans[::-1])), 2)
print(e)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
G = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    used[b] = 1
root = used.index(0)

dist = [0]*n
def rec(cur, depth):
    dist[cur] = max(dist[cur], depth)
    for to in G[cur]:
        rec(to, depth+1)

rec(root, 0)

par = [0]*n
for from_ in range(n):
    for to in G[from_]:
        if dist[from_] + 1 == dist[to]:
            par[to] = from_+1
print(*par, sep="\n")


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

n,m = map(int, input().split())
G = [[] for i in range(n)]
rG = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    rG[b].append(a)
    used[b] = 1
root = used.index(0)

par = [-1]*n
depth = [-1]*n

def rec(cur):
    if depth[cur] != -1:
        return depth[cur]
    m = 0
    i = -1
    for p in rG[cur]:
        if rec(p)+1 > m:
            i = p
            m = rec(p)+1
    par[cur] = i
    depth[cur] = m
    return m

for i in range(n):
    rec(i)
par = [i+1 for i in par]
print(*par, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import heapq
n ,k = map(int, input().split())

used = []
unused = []
for i in range(n):
    t, d = map(int, input().split())
    unused.append((-d,t))
heapq.heapify(unused)
# 最初の集合
c = Counter()
ans = []
kiso = 0
for i in range(k):
    d, t = heapq.heappop(unused)
    kiso -= d
    c[t] += 1
    heapq.heappush(used,(-d, t))
bonus = len(c)
ans.append(kiso + bonus**2)

for i in range(k):
    # いらないものを抜く
    flag = False
    atode = []
    while used:
        d, t = heapq.heappop(used)
        if c[t] > 1:
            c[t] -= 1
            kiso -= d
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(used, i)
    # 全部の種類が1つしかない場合
    if not flag:break
    # 種類を増やす
    flag = False
    atode = []
    while unused:
        d, t = heapq.heappop(unused)
        if c[t]==0:
            bonus+=1
            kiso += -d
            c[t] += 1
            heapq.heappush(used, (-d, t))
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(unused, i)
    # 種類を増やせなかった場合
    if not flag:break
    ans.append(kiso + bonus**2)
print(max(ans))

Fixed submission:
#参考 https://atcoder.jp/contests/abc116/submissions/4059000
n, k = map(int,input().split())
# 価値の大きい順にソート, おいしさが前に来るようにした
sushi = sorted(list(map(int, input().split()))[::-1] for i in range(n))[::-1]
s = set()
# 二個以上あるものの集合があれば良い,かつ最小順
q = []
kiso = 0
for i in range(k):
    d, t = sushi[i]
    if t in s:
        q.append(d)
    else:
        s.add(t)
    kiso += d
ans = kiso + len(s)**2

# 減らせる ∧ 増やせる
i = k
while i < n and q:
    d, t = sushi[i]
    if t not in s:
        s.add(t)
        kiso += -q.pop()+d
        ans = max(ans, kiso+len(s)**2)
        continue
    i+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = np.array(list(map(int, input().split())))

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

    for i in range(n):
        for j in range(1,k+1):
            if i+j < n:
                dp[i+j] = min(dp[i+j], dp[i]+abs(hs[i]-hs[i+j]))
    print(int(dp[-1]))

if __name__ == "__main__":
    main()

Fixed submission:
INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def main():
    n, k = map(int, input().split())
    hs = np.array(list(map(int, input().split())))

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

    for i in range(n):
        for j in range(1,k+1):
            if i+j < n:
                dp[i+j] = min(dp[i+j], dp[i]+abs(hs[i]-hs[i+j]))
    print(int(dp[-1]))

if __name__ == "__main__":
    main()

Fixed submission:
INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

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

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

if __name__ == "__main__":
    main()

Fixed submission:
INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
hs = list(map(int, input().split()))

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

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

Fixed submission:
INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, ww = map(int, input().split())

# dp = [0]*(ww+1)
dp = np.zeros(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    for j in range(ww-w+1)[::-1]:
        if dp[j] or j==0:
            dp[j+w] = max(dp[j+w], dp[j]+v)
print(int(max(dp)))

Fixed submission:
import numpy as np

n, ww = map(int, input().split())

dp = np.zeros(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)

print(int(max(dp)))

Buggy python submission (verdict: Time Limit Exceeded):
n, ww = map(int, input().split())

dp = [0]*(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    for j in range(ww-w+1)[::-1]:
        if dp[j] or j==0:
            dp[j+w] = max(dp[j+w], dp[j]+v)
print(max(dp))

Fixed submission:
import numpy as np

n, ww = map(int, input().split())

dp = np.zeros(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)

print(int(max(dp)))
Buggy python submission (verdict: Time Limit Exceeded):

n, ww = map(int, input().split())

wv = [list(map(int, input().split())) for i in range(n)]

dp = {0:0}
for w, v in wv:
    dp_next = dp.copy()
    for key in dp:
        dp_next[key+v] = min(dp[key]+ w, dp.get(key+v, float("inf")))
    dp = dp_next
for key in sorted(dp.keys(), reverse=True):
    if dp[key] <= ww:
        print(key)
        exit()

Fixed submission:
n, ww = map(int, input().split())

wv = [list(map(int, input().split())) for i in range(n)]
wv.sort(key=lambda x:x[1])
dp = {0:0}
for w, v in wv:
    dp_next = dp.copy()
    for key in dp:
        dp_next[key+v] = min(dp[key]+ w, dp.get(key+v, float("inf")))
    dp = dp_next
for key in sorted(dp.keys(), reverse=True):
    if dp[key] <= ww:
        print(key)
        exit()