A29212.Hot Start Up - Easy Version

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

否则,需要花费 hotihot_i 的时间。

现在有 nn 个程序需要运行,第 ii 次需要运行的程序类型为 aia_i,每次可以任意选择一个 CPU 运行程序,一个 CPU 同一时间最多运行一个程序。

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

共有 tt 组数据。

1n,k50001 \le n,k \le 50001hoticoldi1091 \le hot_i \le cold_i \le 10^91aik1 \le a_i \le k1t50001 \le t \le 5000k5000\sum k \le 5000n5000\sum n \le 5000

Data Credits: Macw07

输入格式

输入包括多个测试用例。第一行包含一个整数 tt ,表示测试用例的数量(1t1051 \le t \le 10^5)。

每个测试用例的第一行包含两个整数 nnkk1n,k31051 \le n, k \le 3 \cdot 10^5)。

每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n1aik1 \le a_i \le k)。

每个测试用例的第三行包含 kk 个整数 cold1,cold2,,coldkcold_1, cold_2, \ldots, cold_k1coldi1091 \le cold_i \le 10^9)。

每个测试用例的第四行包含 kk 个整数 hot1,hot2,,hotkhot_1, hot_2, \ldots, hot_k1hoticoldi1 \le hot_i \le cold_i)。

保证所有测试用例中 nn 的总和以及 kk 的总和不超过 31053 \cdot 10^5

输出格式

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

对于每一个 Testcase\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

    6
    11
    301
    225
    8
    4999999996
    11
    6
    63

说明/提示

In the first test case, we can do the following:

对于第一个样例,一个可行的方案如下:

  • Run program a1=1a_1 = 1 on CPU 11 . It takes cold1=3cold_1 = 3 seconds to run. 在第一个CPU中运行第一个程序,需要花费三秒钟冷却。
  • Run program a2=2a_2 = 2 on CPU 22 . It takes cold2=2cold_2 = 2 seconds to run. 在第二个CPU中运行第二个程序,需要花费两秒钟冷却。
  • Run program a3=2a_3 = 2 on CPU 22 . The last program run on this CPU was also program 22 , so it takes hot2=1hot_2 = 1 second to run. 在第二个CPU中运行第三个程序,由于第三个CPU刚执行完相同的程序,因此只需要花费一秒钟热启动即可。

In total, we need 3+2+1=63 + 2 + 1 = 6 seconds to run them all. We can show this is optimal. 答案为 66

In the second test case, we can use do the following:

  • Run program a1=1a_1 = 1 on CPU 11 . It takes cold1=5cold_1 = 5 seconds to run.
  • Run program a2=2a_2 = 2 on CPU 22 . It takes cold2=3cold_2 = 3 seconds to run.
  • Run program a3=1a_3 = 1 on CPU 11 . The last program run on this CPU was also program 11 , so it takes hot1=2hot_1 = 2 seconds to run.
  • Run program a4=2a_4 = 2 on CPU 22 . The last program run on this CPU was also program 22 , so it takes hot2=1hot_2 = 1 second to run.

In total, we need 5+3+2+1=115 + 3 + 2 + 1 = 11 seconds. We can show this is optimal.

首页