Hot Start Up（困难版）

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

你有一台配备两个 CPU 的设备，以及编号为 $1$ 到 $k$ 的 $k$ 个程序。

程序 $i$ 在某个 CPU 上运行需要 $cold_i$ 秒。如果该 CPU 上一次运行的程序也是 $i$，本次运行只需要 $hot_i$ 秒，其中 $hot_i\le cold_i$。只有同一个 CPU 的上一次运行记录会产生热启动；另一个 CPU 运行过什么程序不会改变该记录。

给定长度为 $n$ 的程序序列 $a_1,a_2,\ldots,a_n$。你必须按顺序运行这些程序，且后一个程序不能在前一个程序结束之前开始。每次可以选择任意一个 CPU 运行当前程序。

求运行全部程序所需的最少总时间。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例包含四行：

• 第一行包含两个整数 $n,k$；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$；
• 第三行包含 $k$ 个整数 $cold_1,cold_2,\ldots,cold_k$；
• 第四行包含 $k$ 个整数 $hot_1,hot_2,\ldots,hot_k$。

输出格式

对每个测试用例输出一行，表示运行全部程序所需的最少总时间。

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

数据范围

对于所有数据，$1\le t\le10^5$，$1\le n,k\le3\times10^5$，$1\le a_i\le k$，$1\le hot_i\le cold_i\le10^9$。所有测试用例的 $n$ 之和与 $k$ 之和分别不超过 $3\times10^5$。