#6045. 「雅礼集训 2017 Day8」价

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

人类智慧之神 zhangzj 最近有点胖,所以要减肥,他买了 N 种减肥药,发现每种减肥药使用了若干种药材,总共正好有 N 种不同的药材。

经过他的人脑实验,他发现如果他吃下去了 K 0 \leq K \leq N )种减肥药,而这 K 种减肥药使用的药材并集大小也为 K ,这 K 种才会有效果,否则无效。
i 种减肥药在产生效果的时候会使 zhangzj 的体重增加 P_i 斤,显然 P_i 可以小于 0

他想知道,一次吃药最好情况下体重变化量是多少,当然可以一种药也不吃,此时体重不变。 由于某些奥妙重重的情况,我们可以让这 N 种减肥药每一种对应一个其使用的药材,且 N 种减肥药对应的药材互不相同(即有完美匹配)。

输入格式

第一行一个整数 N

接下来 N 行,每行描述一种减肥药,对于一种减肥药,第一个数读入使用的药材个数 t ,接下来 t 个整数表示使用的药材编号,一个药材编号在一行只会出现一次。
最后一行 N 个整数,第 i 个整数 P_i 表示第 i 种减肥药产生效果时的体重变化量。

输出格式

一行一个整数表示答案。

样例

样例输入

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

样例输出

-3

数据范围与提示

对于 30\% 的数据, N \leq 20
对于另外 10\% 的数据, P_i < 0
对于 100\% 的数据, 1 \leq N \leq 300, |P_i| \leq 1000000