题解 | #【模板】01背包#

import sys


while True:
    try:
        n, V = map(int, input().split())
        lv, lw = [], []
        for i in range(n):
            l = list(map(int, input().split()))
            lv.append(l[0])  
            lw.append(l[1])  

        dp = [0 for _ in range(V + 1)] 
        dp2 =[float("-inf") for _ in range(V+1)]
        dp2[0] =0
        for i in range(n):
		#通过打印dp数组观察，倒序遍历能保证每个物品只用一次，
            for j in range(V, -1, -1): 
                if  lv[i]<=j:
                    #print(lv[i],j)
                    dp[j] = max(dp[j], dp[j - lv[i]] + lw[i]) 
                    dp2[j] = max(dp2[j], dp2[j-lv[i]]+lw[i])
                    #print(dp)
                    #print(dp2)
        print(max(dp))
        print(dp2[-1] if dp2[-1]!=float("-inf") else 0)
        # print(dp)
        # print(dp2)
        # for i in range(n):
        #     for j in range(V+1):
                
        #         if  lv[i]<=j:
                    
        #             dp[j] = max(dp[j], dp[j - lv[i]] + lw[i]) 
        #             #dp2[j] = max(dp2[j], dp2[j-lv[i]]+lw[i])
        #         print(lv[i],j) 
        #         print(dp)

    except:
        break