题目思路

思路：贪心 + multiset（平衡树）

每个模块的插槽中至多可放入一个其他模块，且每个模块至多被放入一个其他模块的插槽内。

先考虑功耗系数更大的模块，使其插槽空间优先被填充。

按照功耗系数从大到小枚举每个模块，对每个模块，找到一个外部体积不大于其插槽空间的其他模块。即找到小于等于该插槽空间的体积最大值。

题目内容

在太空站维护中，工程师需要处理一批功能模块。共有 $n$ 个模块，第 $i$ 个模块有三个参数：外部体积 $A_i$、内部插槽空间 $B_i$（满足 $B_i \le A_i$）以及功耗系数 $C_i$。

初始时所有模块均未嵌套，每个模块的插槽均处于空闲状态，空闲空间越多，产生的额外功耗越高。具体而言，若模块 $i$ 的插槽剩余空间为 $k$，则会产生 $C_i \times k$ 的额外功耗。为降低总功耗，可以将一些模块放入另一些模块的插槽中。将模块 $x$ 放入模块 $y$ 的插槽需要满足 $A_x \le B_y$。放入后，模块 $y$ 的插槽空间将减少 $A_x$，即剩余 $B_y - A_x$；模块 $x$ 自身的插槽不受影响，仍可继续容纳其他模块。每个模块最多只能被放入一个其他模块的插槽，同时每个模块的插槽也最多只能容纳一个模块。此外，一个模块不能放入自身的插槽。

你需要规划一种嵌套方案，使得全部模块的总额外功耗达到最小，并输出这个最小值。

约束：

• 模块数量 $n$ 不超过 $10^5$。
• 所有 $A_i, B_i, C_i$ 均为不超过 $10^5$ 的正整数。
• 对于任意 $i$，都有 $B_i \le A_i$。

输入描述

第一行包含一个正整数 $n$，表示模块的个数。 接下来三行，每行包含 $n$ 个整数，分别表示： 第一行：每个模块的外部体积 $A_1, A_2, \dots, A_n$； 第二行：每个模块的内部插槽空间 $B_1, B_2, \dots, B_n$； 第三行：每个模块的功耗系数 $C_1, C_2, \dots, C_n$。

输出描述

输出一个整数，表示最小的总额外功耗。

样例1

输入

2
5 3
4 2
10 1

输出

12

说明

初始时两个模块的插槽全空，额外功耗分别为 $10 \times 4 = 40$ 和 $1 \times 2 = 2$，总和为 42。可以将 A = 3 的模块放入 B = 4 的模块中（因为 $3 \le 4$），节省功耗 $C \times A = 10 \times 3 = 30$。放入后，B = 4 的模块剩余空间变为 1，额外功耗变为 $10 \times 1 = 10$；另一个模块仍为 $1 \times 2 = 2$，总功耗降为 12。没有更优方案，因此输出 12。

样例2

输入

3
5 5 4
5 5 4
10 9 1

输出

4

说明

三个模块的 $C \times B$ 初始值分别为 50、45、4，总和 99。 模块体积 A 出现了两次 5 和一次 4，即 gt1[5] 为真。 按 $C$ 从大到小处理：

• 对于 $C=10$、$B=5$ 的模块，优先匹配不超过 5 的最大可用 $A$。集合中有 5 和 4，取出 5（虽然等于自己的 $A$，但因 gt1[5] 为真，可以使用另一个体积为 5 的模块）。节省 $10 \times 5 = 50$。
• 对于 $C=9$、$B=5$ 的模块，同样取出剩余的 5，节省 $9 \times 5 = 45$。
• 对于 $C=1$、$B=4$ 的模块，尝试匹配不超过 4 的最大 $A$，仅剩一个 4，且它恰好等于自身的 $A$ 且 gt1[4] 为假，不能自嵌套，向前寻找更小的值无果，无法匹配。 总节省 95，最终额外功耗 $99 - 95 = 4$。实际上形成了前两个模块互相嵌套的状态（A=5 放入 $B=5$，且两个模块满足 $A \le B$），第三个模块独自留下空闲空间 4，产生功耗 $1 \times 4 = 4$。

样例3

输入

4
10 7 5 3
8 7 4 3
5 10 8 2

输出

39

说明

四个模块的初始额外功耗之和为 $5 \times 8 + 10 \times 7 + 8 \times 4 + 2 \times 3 = 148$。 按功耗系数 $C$ 降序依次匹配：

• $C=10$，$B=7$：可用 $A$ 为 10、7、5、3，不超过 7 的最大值为 7，但该模块自己的 $A$ 就是 7 且仅出现一次，不能自用；退而取 5，节省 $10 \times 5 = 50$，集合移除 5。
• $C=8$，$B=4$：剩余 $A$ 为 10、7、3，不超过 4 的最大值为 3，节省 $8 \times 3 = 24$，移除 3。
• $C=5$，$B=8$：剩余 $A$ 为 10、7，取不超过 8 的最大值 7，节省 $5 \times 7 = 35$，移除 7。
• $C=2$，$B=3$：剩余 $A$ 仅有 10，大于 3，无法匹配。 总节省 $50+24+35=109$，最小额外功耗为 $148 - 109 = 39$。

样例4

输入

1
5
3
2

输出

6

说明

只有一个模块，体积 $A=5$，插槽 $B=3$，功耗系数 $C=2$。因为没有其他模块可以嵌套（自身不能放入自身），额外功耗只能为初始值 $2 \times 3 = 6$。