Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    wv = [[int(x) for x in input().split()] for _ in range(N)]

    dp = [[0] * (W + 1) for j in range(N)]

    for j in range(N):
        for i in range(W + 1):
            if j == 0:
                if i < wv[j][0]:
                    continue
                dp[j][i] = wv[j][1]
            else:
                if i < wv[j][0]:
                    dp[j][i] = dp[j - 1][i]
                else:
                    dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - wv[j][0]] + wv[j][1])

    print(max(dp[-1]))

if __name__ == '__main__':
    main()


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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([i, a, b])

    dp = [[0, set()] for _ in range(W + 1)]

    for i in range(1, W + 1):
        ma = 0
        cp = set()
        for j, w, v in shina:
            if i >= w:
                if j not in dp[i - w][1]:
                    tmp = ma
                    ma = max(ma, dp[i - w][0] + v)
                    if tmp != ma:
                        cp.clear()
                        cp = cp | dp[i - w][1]
                        cp.add(j)

        dp[i][0] = ma
        dp[i][1] = dp[i][1] | cp

    print(dp[W][0])


if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N, -1, -1):
        for j in range(W + 1):
            if i == N:
                try:
                    dp[j][i] = 0
                except IndexError:
                    print(j)
            else:
                if shina[i][0] > j:
                    dp[j][i] = dp[j][i + 1]
                else:
                    dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

shina = []
N = 0


@lru_cache(maxsize=None)
def solve(i, j):
    global N
    if i == N:
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    global N
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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


def solve(i, j, shina):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j, shina)

    return max(solve(i + 1, j, shina), solve(i + 1, j - shina[i][0], shina) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W, shina)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

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

def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = 0
    for i in range(2 ** N):
        weight = 0
        value = 0
        for j in range(N):
            if (i >> j) & 1:
                weight += shina[j][0]
                value += shina[j][1]
                if weight > W:
                    value = 0
                    break

        ans = max(ans, value)

    print(ans)

if __name__ == '__main__':
    main()



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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()