Square Graph

Prof. Elephant has a sequence $a\_1, a\_2, \ldots, a\_n$. He used the sequence to generate an undirected graph $G$ with $n$ vertices labeled $1, 2, \ldots, n$.

For each even-length contiguous subsequence $a\_l, a\_{l + 1}, \ldots, a\_{l + 2 k - 1}$, check whether $a\_{l + i - 1} = a\_{l + k + i - 1}$ holds for every $i = 1, 2, \ldots, k$. If it does, Prof. Elephant adds $k$ edges to $G$. The $i$-th edge connects vertices $(l + i - 1)$ and $(l + k + i - 1)$, and its weight is $w\_k$.

Prof. Elephant wants to know the total weight of the minimum spanning forest of $G$.

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

The first line contains an integer $n$ ($2 \leq n \leq 3 \times 10^5$).

The second line contains $n$ integers $a\_1, a\_2, \ldots, a\_n$ ($1 \leq a\_i \leq n$).

The third line contains $\lfloor\frac{n}{2}\rfloor$ integers $w\_1, w\_2, \ldots, w\_{\lfloor\frac{n}{2}\rfloor}$ ($1 \leq w\_i \leq 10^9$).

The sum of $n$ over all test cases does not exceed $3 \times 10^5$.

For each test case, output one integer: the total weight of the minimum spanning forest of $G$.