完全背包问题—优化版本[1维]
n,m=map(int,input().split())
w=[0 for _ in range(n+1)]
v=[0 for _ in range(n+1)]
for x in range(1,n+1):
w[x],v[x]=map(int,input().split())
dp=[0 for _ in range(m+1)]
for x in range(1,n+1):
for y in range(0,m+1):
if y>=w[x]:
dp[y]=max(dp[y],dp[y-w[x]]+v[x])
print(dp[m])