103602: [Atcoder]ABC360 C - Move It

Problem Statement

There are $N$ boxes numbered $1$ to $N$ and $N$ items numbered $1$ to $N$. Item $i$ $(1 \leq i \leq N)$ is in box $A_i$ and has a weight of $W_i$.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is $w$, the cost of the operation is $w$.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

• $ 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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$W_1$ $W_2$ $\ldots$ $W_N$

Output

Print the minimum total cost required to make each box contain exactly one item.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

• Move item $1$ from box $2$ to box $1$. The cost is $33$.
• Move item $3$ from box $3$ to box $4$. The cost is $2$.

The total cost of these two moves is $35$. It is impossible to make each box contain exactly one item with a cost less than $35$, so print $35$.

Sample Input 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

Sample Output 2

17254

问题陈述

有N个盒子，编号为1到N，以及N个物品，编号为1到N。物品i（1≤i≤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