题意简述
给出一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，和一个长度为 $\left\lfloor \dfrac{n}{2} \right\rfloor$ 的序列 $w_1,w_2,\dots,w_{\lfloor \frac{n}{2} \rfloor}$。
定义 $a[L \dots R]$ 表示序列 $a[L]a[L + 1]\dots a[R]$，即 $a$ 的子串 $[L,R]$。
按照如下规则建一张无向图 $G$：如果存在一对整数 $(l,k)$ 满足 $l + 2k - 1 \le n,a[l \dots l + k - 1] = a[l + k \dots l + 2k - 1]$，那么对于 $\forall i \in [0,k)$，在点 $l + i$ 和 $l + k + i$ 之间连一条权值为 $w_k$ 的边。
请求出图 $G$ 的最小生成森林的权值和。
输入格式
本题有多组测试数据。
第一行输入两个整数 $sid,T$，表示测试点编号和数据组数。样例中 $sid = 0$。
对于每组测试数据：
第一行输入一个整数 $n$。
第二行输入 $n$ 个整数，表示 $a_1,a_2,\dots,a_n$。
第三行输入 $\left\lfloor \dfrac{n}{2} \right\rfloor$ 个整数，表示 $w_1,w_2,\dots,w_{\lfloor \frac{n}{2} \rfloor}$。
输出格式
对于每组测试数据，输出一个整数，表示最小生成森林的权值和。
样例输入 0
0 1
8
2 2 5 6 2 5 6 2
5 1 4 4样例输出 0
21样例解释 0
当 $l = 1,k = 1$ 时，$a[1\dots 1] = a[2 \dots 2]$，所以在 $(1,2)$ 之间连权值为 $w_1 = 5$ 的边。
当 $l = 2,k = 3$ 时，$a[2 \dots 4] = a[5 \dots 7]$，所以在 $(2,5),(3,6),(4,7)$ 之间连权值为 $w_3 = 4$ 的边。
当 $l = 3,k = 3$ 时，$a[3 \dots 5] = a[6 \dots 8]$，所以在 $(3,6),(4,7),(5,8)$ 之间连权值为 $w_3 = 4$ 的边。
最小生成森林中包括边 $(1,2),(2,5),(3,6),(4,7),(5,8)$，故权值和为 $21$。
样例输入/输出 1
见选手目录下 mst/mst_sample1.in 和 mst/mst_sample1.out
该样例满足测试点 $1$ 的限制。
样例输入/输出 2
见选手目录下 mst/mst_sample2.in 和 mst/mst_sample2.out
该样例满足测试点 $2 \sim 3$ 的限制。
样例输入/输出 3
见选手目录下 mst/mst_sample3.in 和 mst/mst_sample3.out
该样例满足测试点 $4$ 的限制。
样例输入/输出 4
见选手目录下 mst/mst_sample4.in 和 mst/mst_sample4.out
该样例满足测试点 $5 \sim 7$ 的限制。
样例输入/输出 5
见选手目录下 mst/mst_sample5.in 和 mst/mst_sample5.out
该样例满足测试点 $8 \sim 10$ 的限制。
数据范围与约定
| 测试点编号 | $n \le$ | 特殊性质 |
|---|---|---|
| $1$ | $500$ | 否 |
| $2 \sim 3$ | $4000$ | 否 |
| $4$ | $3 \times 10^5$ | 是 |
| $5 \sim 7$ | $10^5$ | 否 |
| $ 8 \sim 10$ | $3 \times 10^5$ | 否 |
特殊性质：$a_i$ 在 $[1,2]$ 中独立等概率随机选取。
对于所有数据，保证 $1 \le n \le 3 \times 10^5,1 \le T \le 5,1 \le a_i \le n,1 \le w_i \le 10^9$。