CF1799D2.Hot Start Up (hard version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 coldi seconds to run on some CPU. However, if the last program we ran on this CPU was also program i , it only takes hoti seconds ( hoti≤coldi ). 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 coldi seconds the second time.
You are given a sequence a1,a2,…,an of length n , consisting of integers from 1 to k . You need to use your device to run programs a1,a2,…,an in sequence. For all 2≤i≤n , you cannot start running program ai until program ai−1 has completed.
Find the minimum amount of time needed to run all programs a1,a2,…,an in sequence.
输入格式
Input consists of multiple test cases. The first line contains a single integer t , the number of test cases ( 1≤t≤105 ).
The first line of each test case contains n and k ( 1≤n,k≤3⋅105 ).
The second line of each test case contains n integers a1,a2,…,an ( 1≤ai≤k ).
The third line of each test case contains k integers cold1,cold2,…,coldk ( 1≤coldi≤109 ).
The fourth line of each test case contains k integers hot1,hot2,…,hotk ( 1≤hoti≤coldi ).
It is guaranteed the sum of n and the sum of k over all test cases do not exceed 3⋅105 .
输出格式
For each test case, print the minimum time needed to run all programs in the given order.
输入输出样例
输入#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=1 on CPU 1 . It takes cold1=3 seconds to run.
- Run program a2=2 on CPU 2 . It takes cold2=2 seconds to run.
- Run program a3=2 on CPU 2 . The last program run on this CPU was also program 2 , so it takes hot2=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 a1=1 on CPU 1 . It takes cold1=5 seconds to run.
- Run program a2=2 on CPU 2 . It takes cold2=3 seconds to run.
- Run program a3=1 on CPU 1 . The last program run on this CPU was also program 1 , so it takes hot1=2 seconds to run.
- Run program a4=2 on CPU 2 . The last program run on this CPU was also program 2 , so it takes hot2=1 second to run.
In total, we need 5+3+2+1=11 seconds. We can show this is optimal.