#1479. 「KDOI-06-S」消除序列
「KDOI-06-S」消除序列
题目描述
小 M 有一个长度为 的序列 ,初始时,所有元素的值均为 。
你有 种作用在这个序列上的操作:
- 选择一个下标 (),并且将 的值全部设为 ,这种操作的代价是 ;
- 选择一个下标 (),并且将 的值设为 ,这种操作的代价是 ;
- 选择一个下标 (),并且将 的值设为 ,这种操作的代价是 。
现在有 次询问,每次询问中给定一个集合 ,你希望进行若干次操作(可能为 ),使得:序列 中下标位于该集合的元素的值为 ,其余位置的值为 。形式化地说,对于任意 ,若 ,则 ,否则 。 并且,你需要最小化这次询问中所有操作的总代价。
注意,询问是相互独立的,也就是说,每次询问结束后,序列 将会回到初始状态,即所有元素的值全都变为 。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 ,表示序列 的长度。
第二行包含 个非负整数 ,表示第一种操作的代价。
第三行包含 个非负整数 ,表示第二种操作的代价。
第四行包含 个非负整数 ,表示第三种操作的代价。
第五行包含一个正整数 ,表示询问次数。
接下来的 行中,第 行包含以下内容:
- 开头一个非负整数 ,表示第 次询问中集合 的大小;
- 接下来有 个正整数 ,依次表示集合 中每个元素的值,保证对于任意 $1\le i
输出格式
输出到标准输出。
输出共 行,第 行包含一个非负整数,表示第 次询问中操作总代价的最小值。
样例
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