I. 选课

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

题目描述

小王有n门课程可以选修,第i门课程的学分为Ci。小王觉得第i个课程和其他Ai个课程距离太远,在决定选修第i个课程后,不会选修这Ai门课程。保证,对于m属于正整数,m>2,任选m门课程,仅考虑这m门课程的距离关系时,至少有两门课程有且只距离其中一门课程远,或者这m门课程中两两没有距离关系。小王想知道最多能获得多少学分?

输入格式

输入的第一行是一个整数 n。

第 2 行到 第(n+1)行每行一个整数,第 (i+1) 行的整数表示第 i 门课程的学分 Ci

第 (n+2) 行到第 (2*n+1) 行,每行输入Ai和Ai个整数,第 (i+1+n) 行的整数代表第 i 门课程距离哪些课程远。

输出格式

输出一行一个整数代表能获得的最多学分

样例

样例输入

7
1
1
1
1
1
1
1
1 3
1 3
3 1 2 5
3 5 6 7
2 3 4
1 4
1 4 

样例输出

5

数据范围与提示

3<=n<=1e5,0<=Ci<=1023;Ai总和<2n-1