AT_kupc2021_g.Two Step Sort

有 $N$ 个盒子和 $N$ 个球，编号为 1 到 $N$。最初，第 $i$ 个盒子里装着编号为 $P_i$ 的球。每个盒子只能装一个球，开始时所有盒子都是关闭的，可以打开盒子。

接下来将进行两次球的移动操作，每次操作遵循以下步骤：

1. 选择若干盒子打开，每个盒子都有固定的打开成本。
2. 在打开的盒子之间随意移动球，操作完成时，每个盒子必须有一个球。
3. 将所有打开的盒子再次关闭。

第一次操作时，打开第 $i$ 个盒子的成本为 $A_i$；第二次操作时，打开第 $i$ 个盒子的成本为 $B_i$。经过两次操作后，要求第 $i$ 个盒子里装有第 $i$ 个球。请计算达到目标的最低总成本。

输入由标准输入给出：

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出一个整数，表示实现目标的最小总成本。

• $1 \leq N \leq 10^5$
• $1 \leq P_i \leq N$
• 当 $i \neq j$ 时，$P_i \neq P_j$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 所有输入均为整数

示例解释

在第一个移动事件中，打开盒子 2 和 4，把球 1 放入盒子 2，把球 4 放入盒子 4，这样的操作成本是 8。在第二次移动事件中，打开盒子 1、2、3 和 5，把球 1、2、3 和 5 放入相应的盒子中，操作成本为 20。整个过程的总成本为 28，这是满足条件的最小成本。

有时候，初始状态已经满足要求，意味着不需要进行任何移动。

本翻译由 AI 自动生成