← 返回题目列表

Codeforces · 103/E

E. 购买套装

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

十六进制病毒喜欢玩弄数字集——将它们相交,将它们联合起来。在美好的一天,她惊讶地发现她的球形宠物猫 Scuzzy 将所有套装组合在一起并吃了结果!必须尽快采取行动,十六进制冲向市场。

市场有n组号码在售。病毒想要购买以下集合的集合:集合中的集合数量应该与所有购买的集合的并集中的数字数量完全相同。而且,Hexadecimal想买最便宜的合适的集合。

然而没有什么是那么容易的!由于大型机是一个纯粹竞争市场的王国,我们知道任何 k 个集合的并集包含不少于 k 个不同的数字(对于每个正整数 k)。

帮助病毒选择合适的集合集合。该集合可以为空。

输入

第一行包含唯一的数字 n (1 ≤ n ≤ 300) — 市场上可用的套数。

接下来的 n 行描述了商品:首先我们给出 mi (1 ≤ mi ≤ n) — 第 i 个集合中不同数字的数量,然后是 mi 个数字 — 该集合的元素。我们知道集合的元素是不同的正整数并且它们不超过n。

最后一行包含n个绝对值不超过106的整数——每套的价格。

输出

打印一个数字——病毒必须为 k 个集合的集合支付的最低价格,使得集合的集合的并集恰好有 k 个不同的数字 ($$\forall k \geq 0$$)。

示例

输入 #1

3
1 1
2 2 3
1 3
10 20 -3

输出 #1

-3

输入 #2

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1

输出 #2

0

输入 #3

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1

输出 #3

-1