01背包问题—优化版本[1维]
n,m=map(int,input().split())
ws=[0 for _ in range(n+1)]
vs=[0 for _ in range(n+1)]
for x in range(1,n+1):
ws[x],vs[x]=map(int,input().split())
d=[0 for _ in range(m+1)]
for x in range(1,n+1):
for y in range(m,0,-1):
if y>=ws[x]:
d[y]=max(d[y],d[y-ws[x]]+vs[x])
else:
d[y]=d[y]
print(d[m])