← 返回题目

题库练习 Hot Start Up - Hard Version

← 上一题下一题 →

A3160 | $Hot Start Up - Hard Version$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有两个 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$ Data Credits: [Macw07](https://www.acgo.cn/person/929871)。

输入格式

输入包括多个测试用例。第一行包含一个整数 $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$。

输出格式

For each test case, print the minimum time needed to run all programs in the given order. 对于每一个 $\mathtt{Testcase}$，输出一行一个整数，表示运行完所有程序所需要的时间。

输入输出样例

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

C++ 编辑器

输入

输出