Hot Start Up (hard version)

题意翻译

有两个 CPU 和 $k$ 种程序，你可以在 CPU 上运行程序。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 3 \times 10^5$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 10^5$，$\sum k \le 3 \times 10^5$，$\sum n \le 3 \times 10^5$

题目描述

This is a hard version of the problem. The constraints of $ t $ , $ n $ , $ k $ are the only difference between versions. You have a device with two CPUs. You also have $ k $ programs, numbered $ 1 $ through $ k $ , that you can run on the CPUs. The $ i $ -th program ( $ 1 \le i \le k $ ) takes $ cold_i $ seconds to run on some CPU. However, if the last program we ran on this CPU was also program $ i $ , it only takes $ hot_i $ seconds ( $ hot_i \le cold_i $ ). Note that this only applies if we run program $ i $ multiple times consecutively — if we run program $ i $ , then some different program, then program $ i $ again, it will take $ cold_i $ seconds the second time. You are given a sequence $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of integers from $ 1 $ to $ k $ . You need to use your device to run programs $ a_1, a_2, \ldots, a_n $ in sequence. For all $ 2 \le i \le n $ , you cannot start running program $ a_i $ until program $ a_{i - 1} $ has completed. Find the minimum amount of time needed to run all programs $ a_1, a_2, \ldots, a_n $ in sequence.

输入输出格式

输入格式

Input consists of multiple test cases. The first line contains a single integer $ t $ , the number of test cases ( $ 1 \le t \le 10^5 $ ). The first line of each test case contains $ n $ and $ k $ ( $ 1 \le n, k \le 3 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le k $ ). The third line of each test case contains $ k $ integers $ cold_1, cold_2, \ldots, cold_k $ ( $ 1 \le cold_i \le 10^9 $ ). The fourth line of each test case contains $ k $ integers $ hot_1, hot_2, \ldots, hot_k $ ( $ 1 \le hot_i \le cold_i $ ). It is guaranteed the sum of $ n $ and the sum of $ k $ over all test cases do not exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, print the minimum time needed to run all programs in the given order.

输入输出样例

输入样例 #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

说明

In the first test case, we can do the following: - Run program $ a_1 = 1 $ on CPU $ 1 $ . It takes $ cold_1 = 3 $ seconds to run. - Run program $ a_2 = 2 $ on CPU $ 2 $ . It takes $ cold_2 = 2 $ seconds to run. - Run program $ a_3 = 2 $ on CPU $ 2 $ . The last program run on this CPU was also program $ 2 $ , so it takes $ hot_2 = 1 $ second to run. In total, we need $ 3 + 2 + 1 = 6 $ seconds to run them all. We can show this is optimal. In the second test case, we can use do the following: - Run program $ a_1 = 1 $ on CPU $ 1 $ . It takes $ cold_1 = 5 $ seconds to run. - Run program $ a_2 = 2 $ on CPU $ 2 $ . It takes $ cold_2 = 3 $ seconds to run. - Run program $ a_3 = 1 $ on CPU $ 1 $ . The last program run on this CPU was also program $ 1 $ , so it takes $ hot_1 = 2 $ seconds to run. - Run program $ a_4 = 2 $ on CPU $ 2 $ . The last program run on this CPU was also program $ 2 $ , so it takes $ hot_2 = 1 $ second to run. In total, we need $ 5 + 3 + 2 + 1 = 11 $ seconds. We can show this is optimal.

**热启动（困难版本）**

**题意翻译**：

你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。

如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。

否则，需要花费 $hot_i$ 的时间。

现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。

求最短运行完全部程序的时间。

共有 $t$ 组数据。

$1 \le n,k \le 3 \times 10^5$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 10^5$，$\sum k \le 3 \times 10^5$，$\sum n \le 3 \times 10^5$

**题目描述**：

这是一个难题的困难版本。$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$，直到程序 $a_{i - 1}$ 完成为止。

找出按给定顺序运行所有程序 $a_1, a_2, \ldots, a_n$ 所需的最短时间。

**输入输出格式**：

**输入格式**：

输入由多个测试案例组成。第一行包含一个整数 $t$，表示测试案例的数量（$1 \le t \le 10^5$）。

每个测试案例的第一行包含 $n$ 和 $k$（$1 \le n, k \le 3 \times 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 \times 10^5$。

**输出格式**：

对于每个测试案例，打印运行所有程序所需的最短时间。**热启动（困难版本）** **题意翻译**： 你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 3 \times 10^5$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 10^5$，$\sum k \le 3 \times 10^5$，$\sum n \le 3 \times 10^5$ **题目描述**： 这是一个难题的困难版本。$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$，直到程序 $a_{i - 1}$ 完成为止。 找出按给定顺序运行所有程序 $a_1, a_2, \ldots, a_n$ 所需的最短时间。 **输入输出格式**： **输入格式**： 输入由多个测试案例组成。第一行包含一个整数 $t$，表示测试案例的数量（$1 \le t \le 10^5$）。 每个测试案例的第一行包含 $n$ 和 $k$（$1 \le n, k \le 3 \times 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 \times 10^5$。 **输出格式**： 对于每个测试案例，打印运行所有程序所需的最短时间。