D2. Hot Start Up (hard version)time limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is a hard version of the problem. The constraints of t, n, k are the only difference between versions.You have a device with two CPUs. You also have k programs, numbered 1 through k, that you can run on the CPUs. The i-th program (1 \le i \le k) takes cold_i seconds to run on some CPU. However, if the last program we ran on this CPU was also program i, it only takes hot_i seconds (hot_i \le cold_i). Note that this only applies if we run program i multiple times consecutively  — if we run program i, then some different program, then program i again, it will take cold_i seconds the second time.You are given a sequence a_1, a_2, \ldots, a_n of length n, consisting of integers from 1 to k. You need to use your device to run programs a_1, a_2, \ldots, a_n in sequence. For all 2 \le i \le n, you cannot start running program a_i until program a_{i - 1} has completed.Find the minimum amount of time needed to run all programs a_1, a_2, \ldots, a_n in sequence.InputInput consists of multiple test cases. The first line contains a single integer t, the number of test cases (1 \le t \le 10^5).The first line of each test case contains n and k (1 \le n, k \le 3 \cdot 10^5).The second line of each test case contains n integers a_1, a_2, \ldots, a_n (1 \le a_i \le k).The third line of each test case contains k integers cold_1, cold_2, \ldots, cold_k (1 \le cold_i \le 10^9).The fourth line of each test case contains k integers hot_1, hot_2, \ldots, hot_k (1 \le hot_i \le cold_i).It is guaranteed the sum of n and the sum of k over all test cases do not exceed 3 \cdot 10^5.OutputFor each test case, print the minimum time needed to run all programs in the given order.ExampleInput
93 21 2 23 22 14 21 2 1 25 32 14 31 2 3 1100 100 1001 1 15 22 1 2 1 165 4554 75 31 3 2 1 22 2 21 1 15 11 1 1 1 110000000009999999995 61 6 1 4 13 6 4 1 4 51 1 1 1 4 11 334 5 61 2 38 33 3 3 1 2 3 2 110 10 810 10 5Output
6
11
301
225
8
4999999996
11
6
63
NoteIn the first test case, we can do the following:   Run program a_1 = 1 on CPU 1. It takes cold_1 = 3 seconds to run.  Run program a_2 = 2 on CPU 2. It takes cold_2 = 2 seconds to run.  Run program a_3 = 2 on CPU 2. The last program run on this CPU was also program 2, so it takes hot_2 = 1 second to run. In total, we need 3 + 2 + 1 = 6 seconds to run them all. We can show this is optimal.In the second test case, we can use do the following:   Run program a_1 = 1 on CPU 1. It takes cold_1 = 5 seconds to run.  Run program a_2 = 2 on CPU 2. It takes cold_2 = 3 seconds to run.  Run program a_3 = 1 on CPU 1. The last program run on this CPU was also program 1, so it takes hot_1 = 2 seconds to run.  Run program a_4 = 2 on CPU 2. The last program run on this CPU was also program 2, so it takes hot_2 = 1 second to run. In total, we need 5 + 3 + 2 + 1 = 11 seconds. We can show this is optimal.
93 21 2 23 22 14 21 2 1 25 32 14 31 2 3 1100 100 1001 1 15 22 1 2 1 165 4554 75 31 3 2 1 22 2 21 1 15 11 1 1 1 110000000009999999995 61 6 1 4 13 6 4 1 4 51 1 1 1 4 11 334 5 61 2 38 33 3 3 1 2 3 2 110 10 810 10 5
6 11 301 225 8 4999999996 11 6 63 
['data structures', 'dp', '*2100']