AT_abc404_d.[ABC404D] Goin' to the Zoo

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 AtCoder 国度有 $N$ 个动物园，编号从 $1$ 到 $N$ 。 $i$ 号动物园的门票费用是 $C_i$ 元。

高桥先生喜欢 $M$ 种动物，编号从 $1$ 到 $M$ 。

第 $i$ 种动物在 $K_i$ 个不同的动物园中被展出，分别是 $A_{i,1},A_{i,2},\cdots,A_{i, K_i}$ 号动物园。

高桥想要在游览过程中观赏每种他喜欢的动物至少两次，请问他为了达成这个目标最少要花多少元去买门票？

如果游览了同一个动物园多次，我们认为动物园中的动物也被观赏了多次。

输入格式

第一行两个整数 $N,M(1\le N\le 10,1\le M\le 100)$ 。
第二行 $N$ 个整数 $C_1,C_2,\cdots,C_N(0\le C_i\le 10^9)$ 。
接下来 $M$ 行，第 $i$ 行 $K_i+1$ 个整数，第一个数为 $K_i(1\le K_i\le N)$ ，后面 $K_i$ 个数为 $A_{i,1},A_{i,2},\cdots,A_{i,K_i}$ 。

输出格式

输出一个整数表示需要的最小费用。

输入输出样例

输入#1

4 3
1000 300 700 200
3 1 3 4
3 1 2 4
2 1 3

输出#1

输入#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

说明/提示

样例 1 解释

高桥可以选择：

前往动物园 $3$ 两次，前往动物园 $4$ 两次，总共观赏了 $1$ 号动物 $4$ 次， $2$ 号动物 $2$ 次， $3$ 号动物 $2$ 次。

共花费了 $1800$ 元，可以证明这是可能的最小花费。

样例 2 解释

高桥可以选择：

前往动物园 $7$ 两次，观赏了所有动物两次。

共花费了 $2000$ 元，可以证明这是可能的最小花费。

By chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页