Buggy python submission (verdict: Time Limit Exceeded):
N, W = list(map(int, input().split()))

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# print(dp)
# print(weight)
# print(value)
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])




Fixed submission:
N, W = list(map(int, input().split()))

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = list(map(int, input().split()))

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)




ans = dfs(0, 0, 0)

print(ans)


Fixed submission:
N, W = list(map(int, input().split()))

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])