分数: 250 点
问题陈述
有 N 盒子编号 1 to N 和 N 项目编号 1 to N。项目 i (1 \leq i \leq N) 装在盒子里 A_i 的重量为 W_i.
您可以重复执行选择项目并将其移动到另一个框的操作零次或多次。如果被移动物品的重量为 w,操作成本为 w.
求使每个盒子恰好包含一件物品所需的最低总成本。
约束
- 1 \leq N \leq 10^{5}
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N W_1 W_2 \ldots W_N
输出
打印使每个盒子只包含一件物品所需的最低总成本。
示例输入 1
5 2 2 3 3 5 33 40 2 12 16
示例输出 1
35
通过以下两个步骤,您可以使每个盒子只包含一个项目:
- 移动项目 1 从盒子里 2 到盒子 1。成本是 33.
- 移动项目 3 从盒子里 3 到盒子 4。成本是 2.
这两次移动的总成本是 35。不可能使每个盒子恰好包含一件成本低于 35,所以打印 35.
示例输入 2
12 3 6 7 4 12 4 8 11 11 1 8 11 3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309
示例输出 2
17254