P9744 “KDOI-06-S” Elimination Sequence

Little M has a sequence $v_1, v_2, \ldots, v_n$ of length $n$. Initially, all elements are $1$. You have $3$ types of operations on this sequence: 1. Choose an index $i$ ($1 \le i \le n$), and set $v_1, v_2, \ldots, v_i$ all 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$. Now there are $q$ queries. In each query, you are given a set $P$. You want to perform some operations (possibly $0$ operations) so that: the elements whose indices belong to this set have value $1$, and all other positions have value $0$. **Formally, for any $\bm{1 \le i \le n}$, if $\bm{i \in P}$ then $\bm{v_i = 1}$, otherwise $\bm{v_i = 0}$.** You also need to minimize the total cost of all operations in this query. Note that the queries are independent. That is, after each query ends, the sequence $v$ returns to the initial state, where all elements become $1$ again.

Read input from standard input. The first line contains a positive integer $n$, denoting the length of the sequence $v$. The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, denoting the cost of the first type of operation. The third line contains $n$ non-negative integers $b_1, b_2, \ldots, b_n$, denoting the cost of the second type of operation. The fourth line contains $n$ non-negative integers $c_1, c_2, \ldots, c_n$, denoting the cost of the third type of operation. The fifth line contains a positive integer $q$, denoting the number of queries. In the following $q$ lines, the $i$-th line contains: - A leading non-negative integer $m$, denoting the size of set $P$ in the $i$-th query. - Then $m$ positive integers $p_1, p_2, \ldots, p_m$, in order, denoting each element in set $P$. It is guaranteed that for any $1 \le i < m$, $p_i < p_{i+1}$.

Write to standard output. Output $q$ lines. The $i$-th line contains a non-negative integer, denoting the minimum total cost of operations in the $i$-th query.

**[Sample Explanation #1]** For the first query, you can perform the following operations in order: - Perform operation $1$ at $i = 4$. After that, the sequence $v$ becomes $[0, 0, 0, 0, 1]$, with cost $0$. - Perform operation $3$ at $i = 4$. After that, the sequence $v$ becomes $[0, 0, 0, 1, 1]$, with cost $2$. - Perform operation $2$ at $i = 5$. After that, the sequence $v$ becomes $[0, 0, 0, 1, 0]$, with cost $5$. So the total cost is $0 + 2 + 5 = 7$. It can be proven that there is no smaller total cost. **[Sample Explanation #3]** For the only query in this sample, you can choose to perform operation $1$ at $i = 10$, with total cost $a_{10} = 7$. **[Sample #4]** See `reserve/reserve4.in` and `reserve/reserve4.ans` under the contestant directory. **[Sample #5]** See `reserve/reserve5.in` and `reserve/reserve5.ans` under the contestant directory. This sample satisfies the constraints of test points $8 \sim 11$. **[Sample #6]** See `reserve/reserve6.in` and `reserve/reserve6.ans` under the contestant directory. This sample satisfies the constraints of test points $14 \sim 15$. **[Sample #7]** See `reserve/reserve7.in` and `reserve/reserve7.ans` under the contestant directory. This sample satisfies the constraints of test point $16$. **[Sample #8]** See `reserve/reserve8.in` and `reserve/reserve8.ans` under the contestant directory. This sample satisfies the constraints of test points $17 \sim 20$. *** **[Constraints]** Let $\sum m$ be the sum of all $m$ over all queries within one test case. It is guaranteed for all data that: $1 \leq n \leq 5 \times 10^5$, $0 \le m \le n$, $0 \leq \sum m \leq 5 \times 10^5$, $1 \le q \le \max(n, \sum m)$, $0 \le a_i, b_i, c_i \le 10^9$, $1 \le p_i \le n$. | Test Point ID | $n \le$ | $m \le$ | $\sum m \le$ | Special Property | |:--:|:--:|:--:|:--:|:--:| | $1 \sim 2$ | $5 \times 10^5$ | $0$ | $0$ | No | | $3 \sim 4$ | $7$ | $7$ | $15$ | No | | $5 \sim 6$ | $2 \times 10^3$ | $1$ | $2 \times 10^3$ | No | | $7$ | $2 \times 10^3$ | $2 \times 10^3$ | $2 \times 10^3$ | Yes | | $8 \sim 11$ | $2 \times 10^3$ | $2 \times 10^3$ | $2 \times 10^3$ | No | | $12 \sim 13$ | $5 \times 10^4$ | $5 \times 10^4$ | $5 \times 10^4$ | No | | $14 \sim 15$ | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | No | | $16$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | Yes | | $17 \sim 20$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | No | Special property: for any $1 \le i \le n$, it is guaranteed that $c_i = 0$. **[Hint]** The input and output sizes of this problem are large, so please use an appropriate I/O method. Translated by ChatGPT 5