说明

算法训练&nbsp Buying&nbsp Sets&nbsp  

时间限制：2.0s&nbsp  &nbsp 内存限制：256.0MB

 &nbsp  &nbsp

问题描述

　　给定n个集合,&nbsp 要求选出其中某些集合,&nbsp 使得这些集合的并集的势,&nbsp 等于选出的集合的数目.

　　对于任意的k(1< =k< =n),&nbsp 满从中选出任意k个集合,&nbsp 这k个集合的并集的势一定大于等于k.

　　每个集合有一个权值,&nbsp 每个选择方案的代价是所选的集合的权值的和.

　　请输出代价最小的选择方案的代价.

　　当然,&nbsp 不选择任何一个集合是一个可行的方案(权值和为0),&nbsp 但不一定最优(权值和可以为负).

输入格式

　　第一行一个正整数n(1< =n< =300),&nbsp 为集合个数.

　　在接下来n行中,&nbsp 第i行描述第i个集合:

　　首先给出一个正整数m[i]为该集合的势,&nbsp 显然1< =m[i]< =n.

　　接下来m[i]个在1到n之间的整数,&nbsp 表示该集合中的元素.

　　最后一行n个整数,&nbsp 为每个集合的权值,&nbsp 绝对值不超过1e6.

输出格式

　　仅一个整数,&nbsp 为代价最小的选择方案的代价.

样例输入

3

1&nbsp 1

2&nbsp 2&nbsp 3

1&nbsp 3

10&nbsp 20&nbsp -3

样例输出

-3

样例输入

5

2&nbsp 1&nbsp 2

2&nbsp 2&nbsp 3

2&nbsp 3&nbsp 4

2&nbsp 4&nbsp 5

2&nbsp 5&nbsp 1

1&nbsp -1&nbsp 1&nbsp -1&nbsp 1

样例输出

0

样例输入

5

2&nbsp 1&nbsp 2

2&nbsp 2&nbsp 3

2&nbsp 3&nbsp 4

2&nbsp 4&nbsp 5

2&nbsp 5&nbsp 1

-1&nbsp 1&nbsp -1&nbsp 1&nbsp -1

样例输出

-1