CF1799D1 Hot Start Up (easy 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$）。注意，只有连续多次在同一个 CPU 上运行程序 $i$ 时才适用这个规则——如果运行程序 $i$，然后运行了其他程序，再运行程序 $i$，则第二次运行仍然需要 $cold_i$ 秒。 你得到了一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，其中每个 $a_i$ 是 $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 5000$）。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 5000$）。 每组测试数据的第二行包含 $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$ 的总和不超过 $5000$。

对于每组测试数据，输出依次运行所有程序所需的最少时间。

在第一个测试用例中，可以这样操作： - 在 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 翻译