题目描述

小 B 有 $N$ 个下属，现小 B 要带着一些下属让别人拍照。

有 $M$ 个人，每个人都愿意付给小 B 一定钱来和 $N$ 个下属中的一些人进行合影。如果这一些下属没带齐那么就不能拍照，小 B 也不会得到钱。

注意：带下属不是白带的！！！对于每个下属，如果他带了那么小 B 需要给他一些钱，保证当他拍照时配合。

输入格式

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

输出格式

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

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

17

提示

对于 $10\%$ 的数据每个人都要求让全部 $N$ 个人合影。

对于 $30\%$ 的数据 $N, M\le 15$。

另有 $10\%$ 的数据答案为 $0$。

对于 $50\%$ 的数据 $N, M\le 40$。

另有 $10\%$ 的数据每个人只愿意拍一个人。

对于 $100\%$ 的数据 $1\leq N, M\le100$，费用是 $[1, 5\times 10^8]$ 间的整数。