Minimum Effort Elephant Parade Reordering

A parade of all elephants is to commence soon at the Byteotian zoo. Initially, the elephants line up in a given order, but the manager desires a different order. To achieve this, the only allowed operation is to swap any pair of elephants (they do not have to be adjacent). However, each swap incurs a cost equal to the sum of the masses of the two elephants being swapped.

The task is to compute the minimum total effort required to rearrange the elephants from their current order to the manager's desired order. Note that the elephants can be rearranged by considering cycles in the permutation of positions. For each cycle of length \(k\) with total mass \(S\) and minimum mass in the cycle \(m\), there are two strategies:

• Directly rearrange the cycle at a cost of \(S + (k-2)\,m\).
• Alternatively, use the globally lightest elephant of mass \(g\) (with \(g \le m\)) to help rearrange the cycle at a cost of \(S + m + (k+1)\,g\).

The minimum cost for a cycle is the minimum of these two strategies. The answer is obtained by summing the minimal cost for each cycle.

inputFormat

The input consists of four lines:

• The first line contains a single integer \(n\) representing the number of elephants.
• The second line contains \(n\) integers where the \(i\)-th number is the mass of the elephant with ID \(i\) (\(1 \le i \le n\)).
• The third line contains a permutation of \(n\) integers representing the current order of elephant IDs.
• The fourth line contains a permutation of \(n\) integers representing the desired order of elephant IDs.

outputFormat

Output a single integer: the minimum total effort required to reorder the elephants according to the desired order.

sample

4
1000 2000 3000 4000
1 2 3 4
4 3 2 1

10000