코끼리

바이트 동물원에서 곧 모든 코끼리가 참여하는 퍼레이드가 시작된다. 동물원 직원들은 이 거대한 동물들을 한 줄로 세웠는데, 이 줄이 퍼레이드의 시작을 장식하기로 되어 있기 때문이다.

그런데 퍼레이드에 직접 나온 관리자는 눈앞의 순서가 마음에 들지 않았다. 그는 자신이 생각한 순서대로 세우면 코끼리들이 가장 위엄 있게 보일 것이라며, 직원들에게 그 순서대로 다시 배치하라고 지시했다.

움직이는 코끼리 무리는 큰 혼란을 일으킬 수 있으므로, 직원들은 한 번에 한 쌍씩 자리를 맞바꾸는 방식으로 재배치하기로 했다. 다행히 두 코끼리는 줄에서 서로 인접해 있지 않아도 자리를 바꿀 수 있다. 하지만 코끼리를 움직이게 하는 일은 생각만큼 쉽지 않다. 실제로 드는 노력은 그 동물의 몸무게에 비례한다. 따라서 몸무게가 각각 $m_1$, $m_2$인 두 코끼리의 자리를 맞바꾸는 데 드는 노력은 $m_1 + m_2$로 어림할 수 있다. 관리자가 원하는 순서로 코끼리들을 재배치하는 데 필요한 최소 노력은 얼마인가?

다음을 수행하는 프로그램을 작성하라.

• 모든 코끼리의 몸무게와, 줄에서의 현재 순서 및 원하는 순서를 읽는다.
• 초기 순서에서 원하는 순서로 이어지는 코끼리 교환의 순서(sequence)를, 모든 교환에 드는 노력의 합이 최소가 되도록 정한다.
• 그 최소 노력의 합을 출력한다.

첫째 줄에는 동물원에 있는 코끼리의 수를 나타내는 정수 $n$ ($2 \le n \le 10^6$)이 주어진다. 편의상 코끼리에는 $1$부터 $n$까지 번호가 매겨져 있다고 하자. 둘째 줄에는 각 코끼리의 몸무게(킬로그램 단위)를 나타내는 $n$개의 정수 $m_i$ ($100 \le m_i \le 6500$, $1 \le i \le n$)가 공백 하나로 구분되어 주어진다.

셋째 줄에는 초기 순서로 줄에 선 코끼리들의 번호를 나타내는, 서로 다른 $n$개의 정수 $a_i$ ($1 \le a_i \le n$)가 공백 하나로 구분되어 주어진다. 넷째 줄에는 관리자가 원하는 순서를 나타내는, 서로 다른 $n$개의 정수 $b_i$ ($1 \le b_i \le n$)가 공백 하나로 구분되어 주어진다. 두 수열 $(a_i)$와 $(b_i)$는 서로 다르다고 가정해도 된다.

수열 $(a_i)$가 나타내는 순서에서 $(b_i)$가 나타내는 순서로 코끼리들을 재배치하는 데 드는 최소 노력의 합을 나타내는 정수 하나를 출력한다.

첫 번째(공개) 테스트 케이스에 대한 최적 재배치 중 하나는 다음 세 번의 교환으로 이루어진다.

• 코끼리 $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$이다.