拍照

题目描述

小 B 有 $N$ 个下属,现小 B 要带着一些下属让别人拍照。 有 $M$ 个人,每个人都愿意付给小B一定钱来和 $N$ 个下属中的一些人进行合影。如果这一些下属没带齐那么就不能拍照,小B也不会得到钱。 注意:带下属不是白带的!!!对于每个下属,如果他带了那么小B需要给他一些钱,保证当他拍照时配合。

输入输出格式

输入格式


第 $1$ 行有 $2$ 个正整数 $M$ 和 $N$($0<M,N\le 100$)。接下来的 $M$ 行,每行是一个要求拍照的人的有关数据。第一个数是他同意支付该合影的费用;接着是该合影需要的若干下属的编号,以一个 $0$ 作为行的结束标记。最后一行的 $N$ 个数是带每个下属的费用。

输出格式


一个数,表示最大收益。小 B 可以一个人也不带。

输入输出样例

输入样例 #1

2 3
10 1 2 0
25 2 3 0
5 6 7

输出样例 #1

17

说明

对于 $10\%$ 的数据每个人都要求让全部 $N$ 个人合影。 对于 $30\%$ 的数据 $N\le15,M\le 15$。 另有 $10\%$ 的数据答案为 $0$。 对于 $50\%$ 的数据 $N\le 40,M\le 40$。 另有 $10\%$ 的数据每个人只愿意拍一个人。 对于 $100\%$ 的数据 $M,N\le100$。