CF1799D2 Hot Start Up (hard version)

这是该问题的困难版本。不同版本之间的区别仅在于 $t$、$n$、$k$ 的约束条件。 你有一台带有两个 CPU 的设备。你还有 $k$ 个程序，编号为 $1$ 到 $k$，可以在 CPU 上运行。 第 $i$ 个程序（$1 \le i \le k$）在某个 CPU 上运行需要 $cold_i$ 秒。然而，如果该 CPU 上上一次运行的程序也是第 $i$ 个程序，则只需要 $hot_i$ 秒（$hot_i \le cold_i$）。注意，这只适用于连续多次运行程序 $i$ 的情况——如果先运行程序 $i$，再运行其他程序，然后再次运行程序 $i$，那么第二次运行仍然需要 $cold_i$ 秒。 你得到一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，每个元素都是 $1$ 到 $k$ 之间的整数。你需要使用你的设备，按顺序运行程序 $a_1, a_2, \ldots, a_n$。对于所有 $2 \le i \le n$，在程序 $a_{i-1}$ 运行结束前，不能开始运行程序 $a_i$。 请你计算，按顺序运行所有程序 $a_1, a_2, \ldots, a_n$ 所需的最少时间。

输入包含多组测试数据。第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 10^5$）。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 3 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$）。 每个测试用例的第三行包含 $k$ 个整数 $cold_1, cold_2, \ldots, cold_k$（$1 \le cold_i \le 10^9$）。 每个测试用例的第四行包含 $k$ 个整数 $hot_1, hot_2, \ldots, hot_k$（$1 \le hot_i \le cold_i$）。 保证所有测试用例中 $n$ 的总和与 $k$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一行，表示按顺序运行所有程序所需的最少时间。

在第一个测试用例中，可以这样操作： - 在 CPU 1 上运行程序 $a_1 = 1$，需要 $cold_1 = 3$ 秒。 - 在 CPU 2 上运行程序 $a_2 = 2$，需要 $cold_2 = 2$ 秒。 - 在 CPU 2 上再次运行程序 $a_3 = 2$，由于上一次在该 CPU 上运行的也是程序 2，所以只需 $hot_2 = 1$ 秒。 总共需要 $3 + 2 + 1 = 6$ 秒。可以证明这是最优方案。 在第二个测试用例中，可以这样操作： - 在 CPU 1 上运行程序 $a_1 = 1$，需要 $cold_1 = 5$ 秒。 - 在 CPU 2 上运行程序 $a_2 = 2$，需要 $cold_2 = 3$ 秒。 - 在 CPU 1 上再次运行程序 $a_3 = 1$，由于上一次在该 CPU 上运行的也是程序 1，所以只需 $hot_1 = 2$ 秒。 - 在 CPU 2 上再次运行程序 $a_4 = 2$，由于上一次在该 CPU 上运行的也是程序 2，所以只需 $hot_2 = 1$ 秒。 总共需要 $5 + 3 + 2 + 1 = 11$ 秒。可以证明这是最优方案。 由 ChatGPT 4.1 翻译