Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import os


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import os


def main():
    inp = os.read(0, os.fstat(0).st_size).split()
    n = int(inp[0])
    m = int(inp[1])

    wi = int(inp[2])
    vi = int(inp[3])

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = int(inp[2 * i + 4])
        vi = int(inp[2 * i + 5])
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import os


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import os


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(m + 1 - wi):
        dp[j + wi] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    buffer = map(int, os.read(0, os.fstat(0).st_size).split())
    n, m = next(buffer), next(buffer)
    dp = [0] * (m + 1)
    wi, vi = next(buffer), next(buffer)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = next(buffer), next(buffer)
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    buffer = list(map(int, os.read(0, os.fstat(0).st_size).split()))
    m = buffer[1]
    dp = [0] * (m + 1)
    v1 = buffer[3]
    for i in range(buffer[2], m + 1):
        dp[i] = v1

    for i in range(buffer[0] - 1):
        wi, vi = buffer[4 + 2 * i], buffer[5 + 2 * i]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    buffer = list(map(int, os.read(0, os.fstat(0).st_size).split()))
    m = buffer[1]
    dp = [0] * (m + 1)
    v1 = buffer[3]
    for i in range(buffer[2], m + 1):
        dp[i] = v1

    for i in range(buffer[0] - 1):
        wi, vi = buffer[4 + 2 * i], buffer[5 + 2 * i]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO().readline
main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())

    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        for j in reversed(range(w[i + 1], m + 1)):
            dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())

    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        dp = [dp[j] if j < w[i + 1] else max(v[i + 1] + dp[j - w[i + 1]], dp[j]) for j in range(m + 1)]

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())

    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        next_dp = [0] * (m + 1)
        for j in range(m + 1):
            if j < w[i + 1]:
                next_dp[j] = dp[j]
            else:
                next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
        dp = next_dp

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
def main():
    n, m = map(int, input().split())

    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        next_dp = [0] * (m + 1)
        for j in range(m + 1):
            if j < w[i + 1]:
                next_dp[j] = dp[j]
            else:
                next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
        dp = next_dp

    print(dp[-1])


main()


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
n, m = map(int, input().split())

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [0] * (m + 1)
for j in range(w[0], m + 1):
    dp[j] = v[0]

for i in range(n - 1):
    next_dp = [0] * (m + 1)
    for j in range(m + 1):
        if j < w[i + 1]:
            next_dp[j] = dp[j]
        else:
            next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
    dp = next_dp

print(dp[-1])


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
n, m = map(int, input().split())

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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


Fixed submission:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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