python 代码

v = []
w = []
N, V = tuple(map(int, raw_input().split()))
for i in range(N):
    tmp = raw_input()
    wi, vi = tuple(map(int, tmp.split()))
    v.append(vi)
    w.append(wi)
dp = [0]*(V+1)
for i in range(N):
    for j in range(w[i], V+1):
        dp[j] = max(dp[j], dp[j-w[i]]+v[i])

print dp[-1]