← 返回题目列表

AtCoder · abc404_d

G. 去动物园

中文机器翻译题面 查看原题

分数: 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 日元。