Minimum Operation Cost Transformation Sequence

You are given a sequence \(v_1,v_2,\ldots,v_n\) of length \(n\) where initially \(v_i=1\) for all \(1\le i\le n\). You can perform three types of operations on this sequence:

1. Choose an index \(i\) (\(1\le i\le n\)) and set all the elements \(v_1,v_2,\ldots,v_i\) to 0. The cost of this operation is \(a_i\).
2. Choose an index \(i\) (\(1\le i\le n\)) and set \(v_i\) to 0. The cost of this operation is \(b_i\).
3. Choose an index \(i\) (\(1\le i\le n\)) and set \(v_i\) to 1. The cost of this operation is \(c_i\).

There are \(q\) independent queries. In each query, you are given a set \(P\) (subset of \(\{1,2,\ldots,n\}\)) and you need to perform a sequence of operations (possibly none) so that for every \(1\le i\le n\):

[ v_i=\begin{cases} 1, & \text{if } i\in P,\ 0, & \text{if } i\notin P. \end{cases} ]

Since the initial configuration is all ones, you only need to change the indices where a 0 is desired. Note that using the prefix operation (operation 1) may force you to restore some values back to 1 using operation 3. Formally, if you choose a prefix \(i=k\), then for all \(1\le j\le k\): \(v_j\) becomes 0 and you must use operation 3 on every \(j\) such that \(j\in P\cap [1,k]\) at an extra cost \(c_j\), while indices \(j>k\) remain unchanged (i.e. equal to 1). Alternatively, you may opt not to use the prefix operation at all and simply set every \(j\notin P\) to 0 individually at cost \(b_j\).

Your task is to answer each query by computing the minimum total cost needed to achieve the desired configuration.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1\le n,q\le \text{limits})\).

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\).

The third line contains \(n\) integers: \(b_1, b_2, \ldots, b_n\).

The fourth line contains \(n\) integers: \(c_1, c_2, \ldots, c_n\).

Then \(q\) queries follow. Each query begins with an integer \(m\) \((0\le m\le n)\) indicating the size of set \(P\), followed by \(m\) distinct integers denoting the indices in \(P\). Indices are 1-indexed.

outputFormat

For each query, output a single line containing the minimum total cost to achieve the target configuration.

sample

5 2
3 2 6 5 4
1 2 3 4 5
5 4 3 2 1
2 2 4
3 1 3 5

9
6