分数: 400 点
问题陈述
在AtCoder的国家有 N 动物园,编号 1 to N。动物园入场费 i is C_i 日元。
铃木先生喜欢 M 各种动物、动物 1,\dots,M.
动物 i 可见于 K_i zoos,即动物园 A_{i,1},\dots,A_{i,K_i}.
查找查看全部内容所需的最低总入场费 M 种动物每种至少两次。
如果您多次访问同一个动物园,则每次访问均视为看到一次那里的动物。
约束
- 1 \le N \le 10
- 1 \le M \le 100
- 0 \le C_i \le 10^9
- 1 \le K_i \le N
- 1 \le A_{i,j} \le N
- j \neq j' \Longrightarrow A_{i,j} \neq A_{i,j'}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
C_1 \dots C_N
K_1 A_{1,1} \dots A_{1,K_1}
\vdots
K_M A_{M,1} \dots A_{M,K_M}
输出
输出最低总入场费。
示例输入 1
4 3 1000 300 700 200 3 1 3 4 3 1 2 4 2 1 3
示例输出 1
1800
例如下面的时间表实现了看到动物 1,2,3 各至少两次,总共 1800 日元:
- 去动物园 3。支付 700 日元和看动物 1 和 3.
- 去动物园 3。支付 700 日元和看动物 1 和 3.
- 去动物园 4。支付 200 日元和看动物 1 和 2.
- 去动物园 4。支付 200 日元和看动物 1 和 2.
示例输入 2
7 6 500 500 500 500 500 500 1000 3 1 2 7 3 2 3 7 3 3 4 7 3 4 5 7 3 5 6 7 3 6 1 7
示例输出 2
2000
参观动物园 7 两次,你可以看到动物 1,2,3,4,5,6 各两次,总共 2000 日元。