这是问题的困难版本。 $$$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$$$ 秒。
给定一个序列 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$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$$$。
输出
对于每个测试用例,打印按给定顺序运行所有程序所需的最短时间。
示例
输入 #1
9 3 2 1 2 2 3 2 2 1 4 2 1 2 1 2 5 3 2 1 4 3 1 2 3 1 100 100 100 1 1 1 5 2 2 1 2 1 1 65 45 54 7 5 3 1 3 2 1 2 2 2 2 1 1 1 5 1 1 1 1 1 1 1000000000 999999999 5 6 1 6 1 4 1 3 6 4 1 4 5 1 1 1 1 4 1 1 3 3 4 5 6 1 2 3 8 3 3 3 3 1 2 3 2 1 10 10 8 10 10 5
输出 #1
6 11 301 225 8 4999999996 11 6 63
注意
在第一个测试用例中,我们可以执行以下操作:
- 在 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$$$ 秒。我们可以证明这是最优的。