← 返回题目列表

Codeforces · 1799/D1

D1. 热启动(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。 $$$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 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$$$。

输出

对于每个测试用例,打印按给定顺序运行所有程序所需的最短时间。

示例

输入 #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$$$ 秒。我们可以证明这是最优的。