Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(range(item[i][0], min(w+1, x+item[i][0]+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    print(max(dp))

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(range(item[i][0], min(w+1, x+item[i][0]+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    ans = 0
    for i in reversed(range(w+1)):
        if dp[i] > ans:
            ans = dp[i]
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    for i in range(n):
        for j in reversed(range(item[i][0], w+1)):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
    print(dp[w])

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    dp = [[0, 0]]
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        dp.sort()
        x = len(dp)
        for j in reversed(range(x)):
            p = dp[j][0] + item[i][0]
            q = dp[j][1] + item[i][1]
            if p > w:
                continue
            f = True
            for k in range(j+1, x):
                if dp[k][0] == p:
                    dp[k][1] = max(dp[k][1], q)
                    f = False
            if f:
                dp.append([p, q])
    dp.sort(key=lambda x: x[1], reverse=True)
    print(dp[0][1])

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, w = map(int, input().split())
    dp = {}
    dp[0] = 0
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        buf = []
        for v in dp.keys():
            if v + item[i][0] > w:
                continue
            if v + item[i][0] in dp.keys() and dp[v] + item[i][1] > dp[v+item[i][0]]:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
            else:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
        for j in range(len(buf)):
            dp[buf[j][0]] = buf[j][1]
    print(max(dp.values()))

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()