hulu 9.16 第三题

input = [
'1 1 2',
'1 1 3',
'1 1 4',
'10	10 20',
'10	10 30',
'10	10 60']

# 前缀和 + 01背包
N, K, T = map(int, '3 3 6'.strip().split())
S = []
P = []
for i in range(N):
    S.append(list(map(int, input[i].split())))
    for k in range(1, K):
        S[i][k] =  S[i][k] + S[i][k - 1]
for i in range(N):
    P.append(list(map(int, input[i + N].split())))
    for k in range(1, K):
        P[i][k] =  P[i][k] + P[i][k - 1]
# [[1, 1, 2], [1, 1, 3], [1, 1, 4]]
# [[10, 10, 20], [10, 10, 30], [10, 10, 60]]
# print(S) # [[1, 2, 4], [1, 2, 5], [1, 2, 6]] # 累加需要技能点
# print(P) # [[10, 20, 40], [10, 20, 50], [10, 20, 80]] # 累加所得提升点 

# dp[j] 表示只给定j个技能点能提升最大多少数据
# dp[j] = max(dp[j], dp[j - S[n][k]] + P[n][k])
# dp 初始化为 0 长度为 T + 1

dp = [0] * (T + 1) # 背包容量从0-T
for n in range(N): # 物品个数: 即技能序列个数，每个技能序列不可以重复使用
    for j in range(T, -1, -1):
        for k in range(K): 
            if j - S[n][k] >= 0: # 背包还有足够的容量/还有足够的技能点
                dp[j] = max(dp[j], dp[j - S[n][k]] + P[n][k])

print(dp[T])