Elephants

A parade of all the elephants is about to begin at the Byteotian zoo. The zoo staff lined the huge animals up in a single row, since this row is meant to open the parade.

The manager, however, came to the parade in person and disliked the order he saw. He insisted on his own arrangement, claiming the elephants would look most majestic that way, and told the staff to reorder them accordingly.

Because a herd of moving elephants can cause chaos, the staff decided to rearrange them by swapping one pair at a time. Fortunately, two elephants do not need to stand next to each other to swap places in the row. Moving an elephant is not as easy as it sounds, though: the effort it takes is proportional to the animal's mass. So the effort of swapping two elephants of masses $m_1$ and $m_2$ can be estimated as $m_1 + m_2$. What is the minimum total effort needed to rearrange the elephants into the order the manager wants?

Write a program that:

• reads the masses of all the elephants together with their current order and desired order in the row,
• finds a sequence of swaps that turns the initial order into the desired order while minimizing the total effort of all swaps,
• prints that minimum total effort.

The first line contains a single integer $n$ ($2 \le n \le 10^6$), the number of elephants in the zoo. For convenience the elephants are numbered from $1$ to $n$. The second line holds $n$ integers $m_i$ ($100 \le m_i \le 6500$ for $1 \le i \le n$), separated by single spaces, giving the mass of each elephant in kilograms.

The third line contains $n$ pairwise distinct integers $a_i$ ($1 \le a_i \le n$), separated by single spaces, listing the elephants in their initial order in the row. The fourth line contains $n$ pairwise distinct integers $b_i$ ($1 \le b_i \le n$), separated by single spaces, listing the elephants in the order the manager wants. You may assume the sequences $(a_i)$ and $(b_i)$ are different.

Print a single integer: the minimum total effort needed to rearrange the elephants from the order given by $(a_i)$ into the order given by $(b_i)$.

For the first (public) test case, one optimal rearrangement uses these three swaps:

• swap elephants $2$ and $5$: effort $2000 + 1600 = 3600$, order becomes 1 4 2 3 6 5,
• swap elephants $3$ and $4$: effort $1200 + 2400 = 3600$, order becomes 1 3 2 4 6 5,
• swap elephants $1$ and $5$: effort $2400 + 1600 = 4000$, order becomes 5 3 2 4 6 1, which is the desired one.

The three efforts add up to $3600 + 3600 + 4000 = 11200$.