#1479. 「KDOI-06-S」消除序列

「KDOI-06-S」消除序列

题目描述

小 M 有一个长度为 nn 的序列 v1,v2,…,vnv_1,v_2,\ldots,v_n,初始时,所有元素的值均为 11。

你有 33 种作用在这个序列上的操作:

  1. 选择一个下标 ii(1≤i≤n1\le i\le n),并且将 v1,v2,…,viv_1,v_2,\ldots,v_i 的值全部设为 00,这种操作的代价是 aia_i;
  2. 选择一个下标 ii(1≤i≤n1\le i\le n),并且将 viv_i 的值设为 00,这种操作的代价是 bib_i;
  3. 选择一个下标 ii(1≤i≤n1\le i\le n),并且将 viv_i 的值设为 11,这种操作的代价是 cic_i。

现在有 qq 次询问,每次询问中给定一个集合 PP,你希望进行若干次操作(可能为 00),使得:序列 vv 中下标位于该集合的元素的值为 11,其余位置的值为 00。形式化地说,对于任意 1≤i≤n\bm{1\le i\le n},若 i∈P\bm{i\in P},则 vi=1\bm{v_i=1},否则 vi=0\bm{v_i=0}。 并且,你需要最小化这次询问中所有操作的总代价。

注意,询问是相互独立的,也就是说,每次询问结束后,序列 vv 将会回到初始状态,即所有元素的值全都变为 11。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 nn,表示序列 vv 的长度。

第二行包含 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示第一种操作的代价。

第三行包含 nn 个非负整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,表示第二种操作的代价。

第四行包含 nn 个非负整数 c1,c2,…,cnc_1,c_2,\ldots,c_n,表示第三种操作的代价。

第五行包含一个正整数 qq,表示询问次数。

接下来的 qq 行中,第 ii 行包含以下内容:

  • 开头一个非负整数 mm,表示第 ii 次询问中集合 PP 的大小;
  • 接下来有 mm 个正整数 p1,p2,…,pmp_1,p_2,\ldots,p_m,依次表示集合 PP 中每个元素的值,保证对于任意 $1\le i

输出格式

输出到标准输出。

输出共 qq 行,第 ii 行包含一个非负整数,表示第 ii 次询问中操作总代价的最小值。

样例

5
1 13 6 0 6
2 4 1 0 5
3 4 1 2 1
7
1 4
2 1 5
1 4
2 2 3
5 1 2 3 4 5
1 5
2 3 4
7
3
7
6
0
0
8
7
10 1 6 9 4 2 4 
0 5 2 3 0 1 4 
4 1 4 1 5 3 5 
6
3 1 3 6 
2 2 6 
4 3 4 5 7 
1 4 
2 3 7 
3 3 5 6
12
8
2
5
5
8
10
6 10 7 2 8 4 6 4 8 7
4 0 6 7 8 4 8 2 10 5
4 10 6 1 4 7 5 3 8 7
1
0
7

题目来源:洛谷 P9744