P10096: 购买套装

传统题
2.000s 时间限制
256MB 内存限制
1 提交
1 解决
【题目描述】
【题目描述】
十六进制病毒喜欢玩数字集——把它们交叉起来，把它们合并起来。在一个美丽的日子里，她惊讶地发现，她的球形宠物猫Scuzzy把所有的东西合而为一，并吃掉了结果!必须尽快采取行动，于是十六进制公司冲进了市场。
市场上有n套数字在售。病毒想要购买以下集合:集合中的集合数量应该与所有已购买集合的并集中的数字数量完全相同。另外，十六进制要买最便宜合适的集合集。
然而，没有什么是那么容易的!由于大型机是一个纯粹竞争市场的王国，我们知道任意k个集合的并集包含不少于k个不同的数字(对于每个正整数k)。
请帮助病毒选择合适的集合。集合可以为空。
【输入】
第一行包含唯一的数字n(1≤n≤300)-市场上可用的套数。
接下来的n行描述商品:首先给我们mi(1≤mi≤n) -第i个集合中不同数字的个数，然后给mi数字-集合的元素。我们知道集合的元素是不同的正整数并且它们不超过n。
最后一行包含n个整数，其绝对值不超过106 -每个集合的价格。
【输出】
输出一个数字-病毒必须为k个集合的集合支付的最小价格，该集合的集合的并集恰好有k个不同的数字()。
【输入样例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
【样例输入】复制
	

	

	
【样例输出】 复制
	

	
【提示】

	Buying Sets




	The Hexadecimal virus loves playing with number sets − intersecting them, uniting them. One beautiful day she was surprised to find out that Scuzzy, her spherical pet cat, united all sets in one and ate the result! Something had to be done quickly and Hexadecimal rushed to the market. 





	The market has n sets of numbers on sale. The virus wants to buy the following collection of sets: the number of sets in the collection should be exactly the same as the number of numbers in the union of all bought sets. Moreover, Hexadecimal wants to buy the cheapest suitable collection of set. 

Yet nothing's so easy! As Mainframe is a kingdom of pure rivalry markets, we know that the union of any k sets contains no less than k distinct numbers (for every positive integer k). 

Help the virus choose the suitable collection of sets. The collection can be empty. 





	

		Input
	

The first line contains the only number n (1≤n≤300) − the number of sets available in the market. 

Next n lines describe the goods: first we are given mi (1≤mi≤n) − the number of distinct numbers in the i-th set, then follow mi numbers − the set's elements. We know that the set's elements are distinct positive integers and they do not exceed n. 

The last line contains n integers whose absolute values do not exceed 106 − the price of each set. 





	

		Output
	

Print a single number − the minimum price the virus will have to pay for such a collection of k sets that union of the collection's sets would have exactly k distinct numbers (). 





	

		Examples
	

	

		

			

				Input
			


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


		

		

			

				Output
			


-3


		

		

			

				Input
			


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


		

		

			

				Output
			


0


		

		

			

				Input
			


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


		

		

			

				Output
			


-1

		

	


	    









	

	
题目类型~

	 	










咻咻~

提交答案
状态