#454. 灵性背包问题

灵性背包问题

问题描述

破除重重难关之后,终于到了收获战利品的时间。

摆在小周面前的是 nn 个不同的物品,编号为从 11nn,每个物品都有一个重量 wiw_i 和一个价值 viv_i ,而小周所带的背包能承受的最大重量为 CC

然而,这些物品并不是简单的战利品:"万物皆有灵, 相依缘相伴",这些物品也有自己的灵性,它们都不希望自己是被后选择的物品,越早选择某个物品,他的实际价值将会越大。准确地说:若背包当前可承受的最大重量为 CnowC_{now},此时将第 ii 个物品放入背包则它的实际价值为:(Cnowwi)vi(C_{now} - w_i) * v_i

现在,小周希望你帮他选择物品,这些物品的总重量不超过 CC,且她能获得的实际价值总和最大。

输入格式

第一行给出两个正整数 nnCC ,分别代表物品的数量和背包能承受的最大重量

第二行给出 nn 个正整数,第 ii 个数 wiw_i 代表第 ii 个物品的重量

第三行给出 nn 个正整数,第 ii 个数 viv_i 代表第 ii 个物品的价值

输出格式

输出小周能获得的战利品的最大总实际价值。

输入样例

5 8 
1 3 4 3 2
2 5 1 2 6

输出样例

56

评测数据规模

对于所有评测数据: 1n,C1041 \le n, C \le 10^4 , 1wiC1 \le w_i \le C, 1vi1041 \le v_i \le 10^4

保证所有答案不超过 2632^{63}

样例解释

先选择第5个物品,再选择第1个物品,最后选择第2个物品,按照此顺序选择则获得的战利品的总实际价值为:(82)6+(821)2+(8213)5=56 (8 - 2) * 6 + (8 - 2 - 1) * 2 + (8 - 2 - 1 - 3) * 5 = 56 , 重量总和为:2 + 1 + 3 < 8。符合题目要求,且可以证明这是当前情况下的最优选择。