B'This 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 <= i <= 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 <= 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 <= i <= 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. Input consists of multiple test cases. The first line contains a single integer t , the number of test cases ( 1 <= t <= 10^5 ). The first line of each test case contains n and k ( 1 <= n, k <= 3 cdot 10^5 ). The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= k ). The third line of each test case contains k integers cold_1, cold_2, ldots, cold_k ( 1 <= cold_i <= 10^9 ). The fourth line of each test case contains k integers hot_1, hot_2, ldots, hot_k ( 1 <= hot_i <= 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 . For each test case, print the minimum time needed to run all programs in the given order. In the first test case, we can do the following: In t'...