【模板】完全背包

import sys

# 空间复杂度使用二维数组
def ks(n, V, P, M):
    dp = [[float("-inf") for _ in range(V+1)] for _ in range(n+1)]
    for x in range(len(dp)):
        dp[x][0] = 0
#     for y in range(len(dp[0])):
#         dp[0][y] = 0
    for i in range(1, n+1):
        for j in range(1, V+1):
            if j >= P[i]:
                for k in range(0, j//P[i]+1):
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*P[i]]+k*M[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(max(max(dp)))
    if dp[-1][-1] == float("-inf"):
        print(0)
    else:
        print(dp[-1][-1])
        
# 通过19/20，算法超时        
def ks_B(n, V, P, M):
    dp = [float("-inf") for _ in range(V+1)]
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(V, -1, -1):
            for k in range(0, j//P[i]+1):
                dp[j] = max(dp[j], dp[j-k*P[i]]+k*M[i])
    print(max(dp))
    if dp[-1] != float("-inf"):
        print(dp[-1])
    else:
        print(0)
    return


# 满足要求
# 思考：容量序列遍历为何可以使用正向序列？而且序列的起点可以为P[i]?
# 完全背包问题，物品i没有数量限制;
# 当 j < P[i]时，容量不足以容纳物品 i，
#   相当于d[i][j] = d[i-1][j], 在O(n)复杂度的算法中也就是不更新内容，所以可以设置起点为P[i]

def ks_C(n, V, P, M):
    dp = [float("-inf") for _ in range(V+1)]
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(P[i], V+1):
            dp[j] = max(dp[j], dp[j-P[i]]+M[i])
    print(max(dp))
    if dp[-1] != float("-inf"):
        print(dp[-1])
    else:
        print(0)
    return


line1 = [int(x) for x in sys.stdin.readline().split()]
n = line1[0]
V = line1[1]


P = [0]
M = [0]
for line in sys.stdin:
    tmp = [int(x) for x in line.split()]
    P.append(tmp[0])
    M.append(tmp[1])
ks_C(n, V, P, M)