Hot Start Up (hard version)
Contest: Codeforces Round 854 by cybercats (Div. 1 + Div. 2)
Difficulty rating: 2100
Tags: data structures, dp

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 \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.

Input format:
Input 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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In 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.

Example input:
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

Example output:
6
11
301
225
8
4999999996
11
6
63

Editorial:
Consider maintaining the following 2-dimensional DP: $$$dp_{i,j}$$$ will be the minimum time needed to run all previous programs such that the last program run on CPU 1 was program $$$i$$$, and the last program run on CPU 2 was program $$$j$$$. Initially we have $$$dp_{0,0} = 0$$$ (here, $$$0$$$ is a placeholder program) and $$$dp_{i,j} = INF$$$ for $$$(i, j) \neq (0, 0)$$$.
When we come to a program $$$x$$$, we can transition as follows. First, create a new DP array $$$ndp$$$, initialized to all $$$INF$$$. Then:
• For all $$$dp_{i,j}$$$ with $$$i \neq x$$$, set $$$ndp_{x,j} = \min(ndp_{x,j}, dp_{i,j} + cold_x)$$$.
• For all $$$dp_{x,j}$$$, set $$$ndp_{x,j} = \min(ndp_{x,j}, dp_{x,j} + hot_x)$$$.
• For all $$$dp_{i,j}$$$ with $$$j \neq x$$$, set $$$ndp_{i,x} = \min(ndp_{i,x}, dp_{i,j} + cold_x)$$$.
• For all $$$dp_{i,x}$$$, set $$$ndp_{i,x} = \min(ndp_{i,x}, dp_{i,x} + hot_x)$$$.
After all updates, replace $$$dp$$$ with $$$ndp$$$.
This works in $$$O(nk^2)$$$. To optimize it, we can notice that after processing a program $$$x$$$, only entries in $$$dp$$$ with the row or column equal to $$$x$$$ will be non-$$$INF$$$. Consider instead the following 1-dimensional DP array: $$$dp_i$$$ contains the minimum time to run previous programs if one CPU last ran program $$$x$$$, and the other last ran program $$$i$$$.
Initially, $$$dp_0 = 0$$$ and all other $$$dp_i = INF$$$. Also, we add a dummy program with ID $$$0$$$, and $$$hot_0 = cold_0 = 0$$$ (this will make implementation easier).
When we come to a program $$$x$$$, again, let's create a new DP array $$$ndp$$$, again initialized to all $$$INF$$$. Then, we can case on whether the previous program was equal to $$$x$$$.
• If the last program run was also $$$x$$$:   For all $$$i$$$, set $$$ndp_i = \min(ndp_i, dp_i + hot_x)$$$.  For all $$$i \neq x$$$, set $$$ndp_x = \min(ndp_x, dp_i + cold_x)$$$.  Set $$$ndp_x = \min(ndp_x, dp_x + hot_x)$$$.
• For all $$$i$$$, set $$$ndp_i = \min(ndp_i, dp_i + hot_x)$$$.
• For all $$$i \neq x$$$, set $$$ndp_x = \min(ndp_x, dp_i + cold_x)$$$.
• Set $$$ndp_x = \min(ndp_x, dp_x + hot_x)$$$.
• Otherwise, let $$$y$$$ be the last program run.   For all $$$i$$$, set $$$ndp_i = \min(ndp_i, dp_i + cold_x)$$$.  For all $$$i \neq x$$$, set $$$ndp_y = \min(ndp_y, dp_i + cold_x)$$$.  Set $$$ndp_y = \min(ndp_y, dp_x + hot_x)$$$.
• For all $$$i$$$, set $$$ndp_i = \min(ndp_i, dp_i + cold_x)$$$.
• For all $$$i \neq x$$$, set $$$ndp_y = \min(ndp_y, dp_i + cold_x)$$$.
• Set $$$ndp_y = \min(ndp_y, dp_x + hot_x)$$$.
This gets us a $$$O(nk)$$$ solution which gets accepted in the easy version.
To optimize it further, we can use a data structure to perform updates (since with each transition we either add some value to every $$$dp$$$ element, or add some value to a single index). It is possible to do this in constant time per update, or using a segment tree or some other range update structure (though this is somewhat overkill). The overall complexity then becomes $$$O(n + k)$$$ or $$$O(n \log k + k)$$$ per test.