Hot Start Up (hard version) (Codeforces 1799D2)
Tags: DP, data structures

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: 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: For each test case, print the minimum time needed to run all programs in the given order.

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.

Sample Inputs:
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

Sample Outputs:
6
11
301
225
8
4999999996
11
6
63

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def debug(func):

    def wrapper(*args, **kwargs):
        res = func(*args, **kwargs)
        print('----------------')
        return res
    return wrapper

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
MOD = int(1000000000.0 + 7)
M9D = int(998244353)
INF = int(1e+20)

def solve():
    (N, K) = MI()
    data = LII()
    ct = LII()
    ht = LII()
    dp = [INF] * K
    dp[data[0] - 1] = ct[data[0] - 1]
    mv = ct[data[0] - 1]
    basic = 0
    for i in range(1, N):
        if data[i] == data[i - 1]:
            basic += ht[data[i] - 1]
        else:
            basic += ct[data[i] - 1]
            dp[data[i - 1] - 1] = min(mv, dp[data[i] - 1] - ct[data[i] - 1] + ht[data[i] - 1])
            mv = min(mv, dp[data[i - 1] - 1])
    print(basic + mv)
N = II()
for _ in range(N):
    solve()

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def debug(func):

    def wrapper(*args, **kwargs):
        res = func(*args, **kwargs)
        print('----------------')
        return res
    return wrapper

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
MOD = int(1000000000.0 + 7)
M9D = int(998244353)
INF = int(1e+20)

def solve():
    (n, k) = MI()
    a = LII()
    c = LII()
    h = LII()
    dp = [INF] * k
    dp[a[0] - 1] = c[a[0] - 1]
    s = c[a[0] - 1]
    t = 0
    for i in range(1, n):
        if a[i] == a[i - 1]:
            t += h[a[i] - 1]
        else:
            t += c[a[i] - 1]
            dp[a[i - 1] - 1] = min(s, dp[a[i] - 1] - c[a[i] - 1] + h[a[i] - 1])
            s = min(s, dp[a[i - 1] - 1])
    print(t + s)
N = II()
for _ in range(N):
    solve()

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def debug(func):

    def wrapper(*args, **kwargs):
        res = func(*args, **kwargs)
        print('----------------')
        return res
    return wrapper

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
MOD = int(1000000000.0 + 7)
M9D = int(998244353)
INF = int(1e+20)

def solve():
    (n, k) = MI()
    a = LGMI()
    c = LII()
    h = LII()
    dp = [INF] * k
    dp[a[0]] = c[a[0]]
    s = c[a[0]]
    t = 0
    for i in range(1, n):
        if a[i] == a[i - 1]:
            t += h[a[i]]
        else:
            t += c[a[i]]
            dp[a[i - 1]] = min(s, dp[a[i]] - c[a[i]] + h[a[i]])
            s = min(s, dp[a[i - 1]])
    print(t + s)
N = II()
for _ in range(N):
    solve()