题解 | #【模板】完全背包#

import sys

s = input().split()

n, V = int(s[0]), int(s[1])
i = 1
things = []
while i <= n:
    things.append(list(map(int, input().split())))
    i += 1

dp = [0 for i in range(V + 1)]
#把这里初始化为负无穷，dp2的首个元素初始化为0只有当j=things[i][0]的时候才可以取到dp2等于0的价值，否则的话，dp2永远是无穷和负无穷比较
dp2 = [float("-inf") for i in range(V + 1)]
dp2[0] =0

for i in range(n):
  #因为物品i的数量是无限制的，只要背包的容量够，就可以一直加，所以用正序遍历，背包容量，这个时候，dp数组的值可以重复利用，同一个物品可以使用多次
    for j in range(V + 1):
        if things[i][0] <= j:
            #print(things[i][0], j)
            #print(dp)
            dp[j] = max(dp[j], dp[j - things[i][0]] + things[i][1])
            dp2[j] = max(dp2[j], dp2[j - things[i][0]] + things[i][1])
print(max(dp))
print(dp2[-1] if dp2[-1]!=float("-inf" ) else 0)
#print(dp2)

# #print(dp)
# print(max(dp))
# if dp[V]==dp[V-1]:
#     print(0)
# else:
#     print(dp[V])