问题描述

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

摆在小周面前的是 $n$ 个不同的物品，编号为从 $1$ 到 $n$，每个物品都有一个重量 $w_i$ 和一个价值 $v_i$ ，而小周所带的背包能承受的最大重量为 $C$ 。

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

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

输入格式

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

第二行给出 $n$ 个正整数，第 $i$ 个数 $w_i$ 代表第 $i$ 个物品的重量

第三行给出 $n$ 个正整数，第 $i$ 个数 $v_i$ 代表第 $i$ 个物品的价值

输出格式

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

输入样例

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

输出样例

56

评测数据规模

对于所有评测数据： $1 \le n, C \le 10^4$ , $1 \le w_i \le C$, $1 \le v_i \le 10^4$。

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

样例解释

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