题目描述

题目译自 XVI OI Olimpiada Informatyczna – I etap Słonie

拜托城动物园即将举行一场盛大的游行，所有大象都将参与其中。动物园员工已说服大象们排成一列，准备迎接游行，这是园长规定的起始阵型。然而，园长亲自到场后，对员工安排的大象顺序颇为不满。他提出了一个自认为最能展现大象风采的顺序，并命令员工按此重新排列。

为避免游行前的混乱，员工决定通过依次交换某些大象对的位置来调整顺序，交换的双方不必相邻。说服一头大象移动所需的努力与它的体重成正比，因此，交换两头体重为 $m_1$ 和 $m_2$ 的大象所需的努力可估算为 $m_1 + m_2$。员工们希望以最小的总努力完成调整，满足园长的要求。

编写程序，完成以下任务：

• 从标准输入读取动物园所有大象的体重、当前顺序和目标顺序。
• 确定一种从当前顺序调整到目标顺序的方案，使所有交换的总努力最小。
• 在标准输出中输出这些努力的总和。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示拜托城动物园的大象数量。为简化，假设大象编号从 $1$ 到 $n$。

第二行包含 $n$ 个整数 $m_i$ $(100 \leq m_i \leq 6500, 1 \leq i \leq n)$，表示各头大象的体重（单位：公斤）。

第三行包含 $n$ 个互不相同的整数 $a_i$ $(1 \leq a_i \leq n)$，表示当前排列中大象的编号顺序。

第四行包含 $n$ 个互不相同的整数 $b_i$ $(1 \leq b_i \leq n)$，表示园长提议的目标排列中大象的编号顺序。

保证序列 $(a_i)$ 和 $(b_i)$ 表示的排列不同。

输出格式

第一行输出一个整数，表示从排列 $(a_i)$ 调整到 $(b_i)$ 所需的最小总努力。

6
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1

11200

一种最优的调整方式是依次交换以下大象对：

• 交换 $2$ 和 $5$，努力为 $2000 + 1600 = 3600$，得到排列 $1 4 2 3 6 5$。
• 交换 $3$ 和 $4$，努力为 $1200 + 2400 = 3600$，得到排列 $1 3 2 4 6 5$。
• 交换 $1$ 和 $5$，努力为 $2400 + 1600 = 4000$，得到排列 $5 3 2 4 6 1$，即目标排列。
  总努力为 $3600 + 3600 + 4000 = 11200$。