P9744 「KDOI-06-S」消除序列

小 M 有一个长度为 $n$ 的序列 $v_1,v_2,\ldots,v_n$，初始时，所有元素的值均为 $1$。 你有 $3$ 种作用在这个序列上的操作： 1. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_1,v_2,\ldots,v_i$ 的值全部设为 $0$，这种操作的代价是 $a_i$； 2. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $0$，这种操作的代价是 $b_i$； 3. 选择一个下标 $i$（$1\le i\le n$），并且将 $v_i$ 的值设为 $1$，这种操作的代价是 $c_i$。 现在有 $q$ 次询问，每次询问中给定一个集合 $P$，你希望进行若干次操作（可能为 $0$），使得：序列 $v$ 中下标位于该集合的元素的值为 $1$，其余位置的值为 $0$。**形式化地说，对于任意 $\bm{1\le i\le n}$，若 $\bm{i\in P}$，则 $\bm{v_i=1}$，否则 $\bm{v_i=0}$。** 并且，你需要最小化这次询问中所有操作的总代价。 注意，询问是相互独立的，也就是说，每次询问结束后，序列 $v$ 将会回到初始状态，即所有元素的值全都变为 $1$。

无

无

**【样例解释 #1】** 对于第一次询问，可以按顺序执行如下操作： + 在 $i=4$ 处执行操作 $1$，在这之后，序列 $v$ 变为 $[0,0,0,0,1]$，代价为 $0$； + 在 $i=4$ 处执行操作 $3$，在这之后，序列 $v$ 变为 $[0,0,0,1,1]$，代价为 $2$； + 在 $i=5$ 处执行操作 $2$，在这之后，序列 $v$ 变为 $[0,0,0,1,0]$，代价为 $5$。 所以总代价为 $0+2+5=7$，可以证明，不存在更小的总代价。 **【样例解释 #3】** 对于这个样例中的唯一一次询问，可以选择在 $i=10$ 处执行操作 $1$，总代价为 $a_{10}=7$。 **【样例 #4】** 见选手目录下的 `reserve/reserve4.in` 与 `reserve/reserve4.ans`。 **【样例 #5】** 见选手目录下的 `reserve/reserve5.in` 与 `reserve/reserve5.ans`。 这个样例满足测试点 $8\sim 11$ 的条件限制。 **【样例 #6】** 见选手目录下的 `reserve/reserve6.in` 与 `reserve/reserve6.ans`。 这个样例满足测试点 $14\sim 15$ 的条件限制。 **【样例 #7】** 见选手目录下的 `reserve/reserve7.in` 与 `reserve/reserve7.ans`。 这个样例满足测试点 $16$ 的条件限制。 **【样例 #8】** 见选手目录下的 `reserve/reserve8.in` 与 `reserve/reserve8.ans`。 这个样例满足测试点 $17\sim 20$ 的条件限制。 *** **【数据范围】** 记 $\sum m$ 为单测试点内所有询问 $m$ 的值之和。 对于所有数据保证：$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$。 | 测试点编号 | $n \le$ | $m \le$ | $\sum m \le$| 是否有特殊性质 | |:--:|:--:|:--:|:--:|:--:| | $1 \sim 2$ | $5 \times 10^5$ | $0$ | $0$ | 否 | | $3 \sim 4$ | $7$ | $7$ | $15$ | 否 | | $5 \sim 6$ | $2 \times 10^3$ | $1$ | $2 \times 10^3$ | 否 | | $7$ | $2 \times 10^3$ | $2 \times 10^3$ | $2 \times 10^3$ | 是 | | $8 \sim 11$ | $2 \times 10^3$ | $2\times 10^3$ | $2 \times 10^3$ | 否 | | $12 \sim 13$ | $5 \times 10^4$ | $5 \times 10^4$ | $5 \times 10^4$ | 否 | | $14 \sim 15$ | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | 否 | | $16$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | 是 | | $17 \sim 20$ | $5 \times 10^5$ | $5 \times 10^5$ | $5 \times 10^5$ | 否 | 特殊性质：对于任意 $1\le i\le n$，保证 $c_i = 0$。 **【提示】** 本题输入输出量较大，请使用适当的 I/O 方式。