정사각형 그래프

엘리펀트 교수에게 수열 $a\_1, a\_2, \ldots, a\_n$이 있다. 그는 이 수열로 정점 번호가 $1, 2, \ldots, n$인 무방향 그래프 $G$를 만들었다.

길이가 짝수인 연속 부분 수열 $a\_l, a\_{l + 1}, \ldots, a\_{l + 2 k - 1}$마다, 모든 $i = 1, 2, \ldots, k$에 대해 $a\_{l + i - 1} = a\_{l + k + i - 1}$이 성립하는지 확인한다. 성립하면 엘리펀트 교수는 $G$에 간선 $k$개를 추가한다. $i$번째 간선은 정점 $(l + i - 1)$과 $(l + k + i - 1)$을 잇고, 가중치는 $w\_k$이다.

엘리펀트 교수는 $G$의 최소 스패닝 포레스트의 총 가중치를 알고 싶어 한다.

여러 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 $n$ ($2 \leq n \leq 3 \times 10^5$)이 주어진다.

둘째 줄에 정수 $a\_1, a\_2, \ldots, a\_n$ ($1 \leq a\_i \leq n$)이 주어진다.

셋째 줄에 정수 $w\_1, w\_2, \ldots, w\_{\lfloor\frac{n}{2}\rfloor}$ ($1 \leq w\_i \leq 10^9$)이 주어진다.

모든 테스트 케이스의 $n$ 합은 $3 \times 10^5$을 넘지 않는다.

각 테스트 케이스마다 $G$의 최소 스패닝 포레스트 총 가중치를 정수 하나로 출력한다.