鱼头买菜

Time Limit: 4000MS

Memory Limit: 131072KB

Description

鱼头有一天想去给鱼儿子做一顿丰盛的大餐。由于他不太会挑菜,所以他决定去超市里买包装好的现成的材料。到了超市,鱼头发现超市里共有n种菜的食材,每种都装在一个保鲜盒中。每一盒都可以做一样菜,包含若干种不同的食材,比如蒜苗、肉丝就放在一个袋子里。并且,不同盒子里可能有相同的食材,鱼头可以将它们放在一起供自己调配。

   由于鱼头是个勤俭节约的好孩子,他想花最少的钱买到尽可能丰富多彩的食材。这个“丰富多彩”就定义为,对于他买的任意k盒,必须包含至少k(k为任意非负整数)种不同的食材,并且,最终买多少盒就要有多少种食材。

   现在告诉你每一盒的营养综合指标Pi(Pi为整数,Pi越小,表示能吸收的营养越多,价值越高),请你帮帮鱼头,他买的食材的营养价值最多可以达到多高?(如果实在没有足够营养的东西,他也可以不买)

Input

有多组输入,每组输入之间以空行隔开。

   每组的第一行:n(1<=n<=300)

   下面n行,每行以mi(1<=mi<=n)开头,表示第i个袋子里有mi种食材,然后mi个正整数a(i,j),表示不同的食材(1<=a(i,j)<=n)。

   最后一行n个数,表示每盒的营养综合指标Pi.

Output

 对每组数据,第一行输出Case数;第二行输出最高营养价值和购买盒数,并以空格隔开;第三行输出购买方案(按盒子编号从小到大输出,若不买,则不输出此行)。

Sample Input

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

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

Sample Output

Case #1:
-3 1
3
Case #2:
0 0

Hint

None

Source

None

提交代码