Submission #39059217

---

Source Code Expand

n, w = map(int, input().split())
h = [0]
v = [0]
for _ in range(n):
    s, t = map(int, input().split())
    h.append(s)
    v.append(t)

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(w + 1):
        if j < h[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            p = dp[i - 1][j]
            q = dp[i - 1][j - h[i]] + v[i]
            dp[i][j] = max(p, q)
ans = 0
for i in range(w + 1):
    ans = max(ans, dp[n][i])
print(ans)

Submission Info

Judge Result