Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    double = 1
    i = 0
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    num = 2**59
    p = 1
    for i in range(59, -1, -1):
        if k >= num:
            k -= num
            p = to[i][p-1]
        num //= 2
    print(p)
        
    

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if a[0] == 1:
        print(1)
        exit(0)
    if a[0] == a[a[0]-1]:
        print(a[0])
        exit(0)
    pos = a[0]
    num = 1
    nums = set([1])
    while pos not in nums:
        nums.add(pos)
        num += 1
        pos = a[pos-1]
    lastnum = pos
    prefix = 0
    pos = 1
    while pos != lastnum:
        prefix += 1
        pos = a[pos-1]
    num -= prefix
    if k > prefix:
        k = (k-prefix)%num+prefix
    pos = 1
    for _ in range(k):
       pos = a[pos-1]
    print(pos)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)



def dfs(p):
    ai = a[p]
    i = bisect_left(dp, ai)
    old = dp[i]
    dp[i] = ai
    ans[p] = bisect_left(dp, INF)-1
    for child in to[p]:
        if ans[child] is None:
            dfs(child)
    dp[i] = old
    
    
        

if __name__ == "__main__":
    n = int(input())
    a = [None] + list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0]= -INF
    q = deque([1])
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))

Fixed submission:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)



def dfs(p):
    ai = a[p]
    i = bisect_left(dp, ai)
    old = dp[i]
    dp[i] = ai
    ans[p] = bisect_left(dp, INF)-1
    for child in to[p]:
        if ans[child] is None:
            dfs(child)
    dp[i] = old
    
    
        

if __name__ == "__main__":
    n = int(input())
    a = [None] + list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0]= -INF
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = [(10**i)%2019 for i in range(n)]
    for i in range(n):
        num += s[n-i-1]*ten[i]
        num %= 2019
        m[num] += 1 
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

Fixed submission:
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = 1
    for i in range(n):
        num += s[n-i-1]*ten
        num %= 2019
        m[num] += 1 
        ten = (ten*10)%2019
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    for i, si in enumerate(s[::-1]):
        num += si*10**i
        num %= 2019
        m[num] += 1 
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

Fixed submission:
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = 1
    for i in range(n):
        num += s[n-i-1]*ten
        num %= 2019
        m[num] += 1 
        ten = (ten*10)%2019
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    k = int(input())
    gcds = list(sorted([gcd(i, j) for i in range(1, k+1) for j in range(1, k+1)]))
    j = 0
    s = list(set(gcds))
    m = k**2-1
    gcdss = [0]*len(s)
    for i, l in enumerate(s):
        while gcds[j] == l:
            j += 1
            gcdss[i] += 1
        if j == m:
            break
    ans = sum([gcd(i, j)*n for i in range(1, k+1) for j, n in zip(s, gcdss)])
    print(ans)
            
    
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)


if __name__ == "__main__":
    main()

Fixed submission:
def main():
    k = int(input())
    gcds = list(sorted([gcd(i, j) for i in range(1, k+1) for j in range(1, k+1)]))
    j = 0
    s = list(sorted(list(set(gcds))))
    m = k**2-1
    gcdss = [0]*len(s)
    flag = False
    for i, l in enumerate(s):
        while gcds[j] == l:
            gcdss[i] += 1
            if j == m:
                flag = True
                break
            j += 1
        if flag:
            break
    ans = sum([gcd(i, p)*n for i in range(1, k+1) for p, n in zip(s, gcdss)])
    print(ans)
            
    
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = list(input())
    count = {"G": 0, "R":0, "B":0}
    for i in s:
        count[i] += 1
    ans = count["G"]*count["R"]*count["B"]
    for j in range(n):
        for i in range(1, n//2+1):
            if j+2*i > n-1:
                continue
            if len(set([s[j], s[j+i], s[j+2*i]])) == 3:
                ans -= 1
    print(ans)
    
    

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    s = list(input())
    ss = list(sorted(list(set(s))))
    s_sorted = list(sorted(s))
    if len(ss) < 3:
        print(0)
        return
    m = n-1
    sn = [0]*3
    j = 0
    flag = False
    for i, si in enumerate(ss):
        while s_sorted[j] == si:
            sn[i] += 1
            if j == m:
                flag = True
                break
            j += 1
        if flag:
            break
    ans = sn[0]*sn[1]*sn[2]
    for d in range(1, n//2+1):
        i = 0
        d2 = 2*d
        ma = n-d2
        while i < ma:
            si, sj, sk = s[i], s[i+d], s[i+d2]
            if si != sj and sj != sk and si != sk:
                ans -= 1
            i += 1
    print(ans)
                

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 2:
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    if n > 2:
        dp[3] = max(a[:3])
        aa = a[0]+a[2]
        for i in range(4, n+1):
            if i%2:
                aa += a[i-1]
                dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
            else:
                dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    if n > 2:
        dp[3] = max(a[:3])
        aa = a[0]+a[2]
        for i in range(4, n+1):
            if i%2:
                aa += a[i-1]
                dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
            else:
                dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    dp[3] = max(a[:3])
    aa = a[0]+a[2]
    for i in range(4, n+1):
        if i%2:
            aa += a[i-1]
            dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
        else:
            dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    if n > 2:
        dp[3] = max(a[:3])
        aa = a[0]+a[2]
        for i in range(4, n+1):
            if i%2:
                aa += a[i-1]
                dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
            else:
                dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[-10**15]*(3) for i in range(n+1)]
    dp[2][0] = a[0]
    dp[2][1] = a[1]
    dp[2][2] = max(a[0], a[1])
    dp[3][0] = max(a[0]+a[1], a[0]+a[2], a[1]+a[2])
    for i in range(4, n+1):
        if i%2:
            dp[i][0] = max(dp[i-1][2], dp[i-2][0]+a[i-1])
        else:
            dp[i][0] = dp[i-2][0]+a[i-2]
            dp[i][1] = dp[i-2][1]+a[i-1]
            dp[i][2] = max(dp[i][0], dp[i][1])
    if n%2:
        print(dp[n][0])
    else:
        print(dp[n][2])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    if n > 2:
        dp[3] = max(a[:3])
        aa = a[0]+a[2]
        for i in range(4, n+1):
            if i%2:
                aa += a[i-1]
                dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
            else:
                dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    x, y = map(int, input().split())
    a = list(map(int, input().split()))
    cost = 10*10
    for i in range(n-1):
        cost = min(cost, k - abs(a[i]-a[i+1]))
    print(min(cost, k-abs(a[0]+k-a[n-1])))

if __name__ == "__main__":
    main()

Fixed submission:
k, n = map(int, input().split())
a = list(map(int, input().split()))
ans = a[-1] - a[0]
for i in range(1, n):
    start = a[i]
    end = a[i-1]+k
    ans = min(ans, end-start)
print(ans)
Buggy python submission (verdict: Runtime Error):
x, y, a, b, c = map(int, input().split())
al = sorted(list(map(int, input().split())), reverse=True)[:x]
bl = sorted(list(map(int, input().split())), reverse=True)[:y]
cl = sorted(list(map(int, input().split())), reverse=True)
ans = 0
xi, yi = 0, 0
for i in cl:
    if al:
        ai = al[-1]
    else:
        ai = 0
    if bl:
        bi = bl[-1]
    else:
        bi = 0
    if ai < bi:
        m = al.pop()
    else:
        m = bl.pop()
    if m < i:
        ans += i
    else:
        ans += m
        break
ans += sum(al)+sum(bl)
print(ans)

Fixed submission:
def main():
    x, y, a, b, c = map(int, input().split())
    al = sorted(list(map(int, input().split())), reverse=True)[:x]
    bl = sorted(list(map(int, input().split())), reverse=True)[:y]
    cl = sorted(list(map(int, input().split())), reverse=True)
    ans = 0
    xi, yi = 0, 0
    for i in cl:
        if al:
            ai = al[-1]
        else:
            ai = 10000000000
        if bl:
            bi = bl[-1]
        else:
            bi = 10000000000
        if ai < bi:
            if al:
                m = al.pop()
            else:
                m = 0
        else:
            if bl:
                m = bl.pop()
            else:
                m = 0
                
        if m < i:
            ans += i
        else:
            ans += m
            break
    ans += sum(al)+sum(bl)
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
x_min = max(int(100/8 * a), int(100/10 * b))
x_max = min(int(100/8 * (a+1)), int(100/10 * (b+1)))
if int(100/8 * a) < int(100/10 * (b+1) and int(100/10 * b) < int(100/8 * (a+1)):
    print(x_min)
else:
    print(-1)


Fixed submission:
a, b = map(int, input().split())
ass = 1 if ((100/8 * (a+1))-int(100/8 * (a+1))) else 0
asss = 1 if ((100/8 * a)-int(100/8 * a)) else 0
bss = 1 if ((100/10 * (b+1))-int(100/10 * (b+1))) else 0
bsss = 1 if ((100/10 * b)-int(100/10 * b)) else 0
As = set(range(int(100/8 * a)+asss, int(100/8 * (a+1))+ ass))
Bs = set(range(int(100/10 * b)+bsss, int(100/10 * (b+1))+bss))
if As & Bs:
    print(min(As&Bs))
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
if a < 1 or b < 1:
    print(-1)
else:
    amin = a*100//8 + ((a*100)%8 and 1)
    amax = (a+1)*100//8 + (max((a+1)*100)%8, 1) or 1)
    bmin = b*100//10 + ((b*100)%10 and 1)
    bmax = (b+1)*100//10 + (max(((b+1)*100)%10, 1) or 1)
    A = set(range(amin, amax))
    B = set(range(bmin, bmax))
    if (A & B):
        print(min(A&B))
    else:
        print(-1)

Fixed submission:
a, b = map(int, input().split())
ass = 1 if ((100/8 * (a+1))-int(100/8 * (a+1))) else 0
asss = 1 if ((100/8 * a)-int(100/8 * a)) else 0
bss = 1 if ((100/10 * (b+1))-int(100/10 * (b+1))) else 0
bsss = 1 if ((100/10 * b)-int(100/10 * b)) else 0
As = set(range(int(100/8 * a)+asss, int(100/8 * (a+1))+ ass))
Bs = set(range(int(100/10 * b)+bsss, int(100/10 * (b+1))+bss))
if As & Bs:
    print(min(As&Bs))
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s = c+s
            else:
                s = s+c
    print(s[::r])
                
            

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
def main():
    s = deque(list(input()))
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s.appendleft(c)
            else:
                s.append(c)
    print("".join(list(s)[::r]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s = c+s
            else:
                s = s+c
    print(s[::r])
                
            

if __name__ == "__main__":
    main()

Fixed submission:
from collections import deque
def main():
    s = deque(list(input()))
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s.appendleft(c)
            else:
                s.append(c)
    print("".join(list(s)[::r]))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
a = [list(map(int, input().split())) for _ in range(3)]
is_bingo = [[False]*3 for _ in range(3)]
n = int(input())
for _ in range(n):
    b = int(input())
    for i, ai in enumerate(a):
        for j, aii in enumerate(ai):
            if aii == b:
                is_bingo[i][j] = True
is_bingo_flat = [j for i in is_bingo for j in i]
for i in range(3):
    if all(is_bingo[i]) or all(list(zip(*is_bingo))[i]):
        print("Yes")
        break
else:
    if all(is_bingo_flat[::3]) or all(is_bingo_flat[2:7::2]):
        print("Yes")
    print("No")

        

Fixed submission:
def main():
    A = [list(map(int, input().split())) for _ in range(3)]
    n = int(input())
    B = [int(input()) for _ in range(n)]
    ans =  [None]*8
    AT = list(zip(*A))
    ans[0] = set(A[0])
    ans[1] = set(A[1])
    ans[2] = set(A[2])
    ans[3] = set(AT[0])
    ans[4] = set(AT[1])
    ans[5] = set(AT[2])
    ans[6] = set([A[i][i] for i in range(3)])
    ans[7] = set([A[i][2-i] for i in range(3)])

    for b in B:
        for a in ans:
            if b in a:
                a -= {b}
                if not a:
                    print("Yes")
                    return
    print("No")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n, m, *a = map(int, open(0).read().split())
new_a = sorted(a, key=lambda x: -x)
sum = 0
for _ in range(m):
    new_a[0] /= 2
    new_a.sort(key=lambda x: -x)
for price in new_a:
    sum += int(price)
print(sum)

Fixed submission:
s = input()
weathers = ['Sunny', 'Cloudy', 'Rainy']
print(weathers[(weathers.index(s)+1)%3])

Buggy python submission (verdict: Runtime Error):
import sys
s = sys.argv
weathers = ['Sunny', 'Cloudy', 'Rainy']
for i, weather in enumerate(weathers):
    if s == weather:
        return weathers[(i+1)%3]

Fixed submission:
s = input()
weathers = ['Sunny', 'Cloudy', 'Rainy']
print(weathers[(weathers.index(s)+1)%3])

Buggy python submission (verdict: Runtime Error):
import sys
s = sys.argv
weathers = ['Sunny', 'Cloudy', 'Rainy']
for i, weather in enumerate(weathers):
    if s == weather:
        return weathers[i+1]

Fixed submission:
s = input()
weathers = ['Sunny', 'Cloudy', 'Rainy']
print(weathers[(weathers.index(s)+1)%3])
Buggy python submission (verdict: Runtime Error):
n, k, q = map(int, input().split())
if k-q >=1:
    for _ in range(q):
        print("Yes")
out = [k-q for _ in range(n)]
for _ in range(q):
    a = int(input())
    out[a] += 1
for i in range(n):
    msg = "Yes" if out[i] >= 1 else "No"
    print(msg)

Fixed submission:
n, k, q = map(int, input().split())
out = [k-q for _ in range(n)]
for _ in range(q):
    a = int(input())-1
    out[a] += 1
for i in range(n):
    msg = "Yes" if out[i] > 0 else "No"
    print(msg)
Buggy python submission (verdict: Runtime Error):
from math import gcd
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ar = a[::-1]
    lgcds = [1]*n
    rgcds = [1]*n
    lgcd, rgcd = a[0], ar[0]
    lgcds[0] = rgcd
    lgcds[1] = lgcd
    rgcds[n-1] = lgcd
    rgcds[n-2] = rgcd
    for i in range(2, n):
        lgcd = gcd(lgcd, a[i])
        rgcd = gcd(rgcd, ar[i])
        lgcds[i] = lgcd
        rgcds[n-1-i] = rgcd
    ans = 1
    for i in range(n):
        gi = gcd(lgcds[i], rgcds[i])
        if gi > ans:
            ans = gi
    print(ans)
    

if __name__ == "__main__":
    main()

Fixed submission:
from fractions import gcd
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ar = a[::-1]
    lgcds = [1]*n
    rgcds = [1]*n
    lgcd, rgcd = a[0], ar[0]
    lgcds[0] = rgcd
    lgcds[1] = lgcd
    rgcds[n-1] = lgcd
    rgcds[n-2] = rgcd
    for i in range(2, n):
        lgcd = gcd(lgcd, a[i-1])
        rgcd = gcd(rgcd, ar[i-1])
        lgcds[i] = lgcd
        rgcds[n-1-i] = rgcd
    ans = 1
    for i in range(n):
        gi = gcd(lgcds[i], rgcds[i])
        if gi > ans:
            ans = gi
    print(ans)
    

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**10
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    di = dp[i]
    hi = h[i]
    for k in range(max(i-K, 0), i):
        a = dp[k]+abs(hi-h[k])
        if di > a:
            di = a
    dp[i] = di
print(dp[n-1])

Fixed submission:
n = int(input())
H = list(map(int, input().split()))
cost = [None]*n
h1 = [None]*(n-1)
h2 = [None]*(n-2) 
one_ago = H[1]
two_ago = H[0]
h1[0] = abs(two_ago-one_ago)
for i in range(2, n):
    new = H[i]
    h1[i-1] = abs(one_ago-new)
    h2[i-2] = abs(two_ago-new)
    two_ago, one_ago = one_ago, new
cost[0], cost[1] = 0, h1[0]
for i in range(2, n):
    cost[i] = min(cost[i-2]+h2[i-2], cost[i-1]+h1[i-1])
print(cost[n-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[None]*3 for _ in range(n)]
dp[0] = abc[0]
K = [[1, 2], [0, 2], [0, 1]]
for i in range(1, n):
    abci = abc[i]
    for j in range(3):
        for k in K[j]:
            dp[i][j] = max(dp[i-1][k[0]]+abci[j], dp[i-1][k[1]]+abci[j])
print(max(dp[-1]))

Fixed submission:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[None]*3 for _ in range(n)]
dp[0] = abc[0]
m = [[0, [1, 2]], [1, [0, 2]], [2, [0, 1]]]
for i in range(1, n):
    abci = abc[i]
    for j, k in m:
        dp[i][j] = max(dp[i-1][k[0]]+abci[j], dp[i-1][k[1]]+abci[j])
print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[None]*(w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
for i in range(1, n+1):
    wi, vi = wv[i-1]
    di = dp[i]
    dio = dp[i-1]
    for j in range(wi):
        di[j] = dio[j]
    for j in range(wi, w+1):
        di[j] = max(dio[j], dio[j-wi]+vi)
print(dp[-1][-1])

Fixed submission:
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

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

Fixed submission:
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

if __name__ == "__main__":
    main()