Gigel 想要测试他的烹饪能力，于是去市场采购一些补给品。市场上共有 $m$ 种物品，在 $n$ 天内以促销礼包的形式出售。在第 $i$ 天，Gigel 有两种选择：要么购买当天提供的促销礼包，要么不买。促销礼包由 $m$ 种物品集合的一个非空子集表示，并且有一个特定的价格。
题目描述
已知 $m$、$n$，以及 $n$ 个促销礼包中每个礼包的价格和组成，求 Gigel 为了买到至少一个每种类型的物品所需要支付的最小价格。
输入格式
输入文件的第一行包含两个数字 $m$ 和 $n$。 接下来的 $n$ 行描述了 $n$ 个促销礼包：第 $i+1$ 行（$1 \le i \le n$）包含 $nr$ 和 $p$，分别表示该天促销礼包中物品的数量及其价格。随后在同一行中，给出了 $nr$ 个数字，代表属于该礼包的物品编号。
输出格式
在输出文件中，打印一个正整数，等于为了买到至少一个每种类型的物品所需要支付的最小价格。
数据范围
- $1 \le m \le 17$，$1 \le n \le 1,000$，$1 \le p \le 1,000,000$
- 输入文件中的所有数字均为正整数。
- 促销礼包必须整套购买。
- 描述某个礼包的物品编号取值范围为 $\{1, 2, \dots, m\}$。
- 保证所有测试用例均有解。
子任务
| 子任务 | 分值 | 额外输入限制 |
|---|---|---|
| 1 | 50 | $m \le 10, n \le 100$ |
| 2 | 80 | $m \le 15, n \le 1,000$ |
| 3 | 100 | $m \le 17, n \le 1,000$ |
样例
输入 1
5 4 3 10 1 3 2 2 8 1 4 3 11 5 4 3 5 27 1 4 2 3 5
输出 1
21
说明
选择第一个和第三个礼包，从而获得 $10+11 = 21$ 的最小成本。注意，Gigel 买到了 1 个 1 型物品，1 个 2 型物品，2 个 3 型物品，1 个 4 型物品和 1 个 5 型物品。