“物品制作能力竞赛”是一项有趣的活动，MyCraft 的玩家可以通过它来挑战彼此，以展示他们对游戏丰富合成系统的了解！MyCraft 中有 $m$ 种不同的物品，内部 ID 编号为 $1$ 到 $m$。只有部分物品可以在游戏世界中找到；我们称这些为原材料。

所有其他物品都必须使用游戏的合成系统制作。每个非原材料物品都有一个配方，即其他物品的列表。为了合成该物品，你必须消耗配方中列出的每种物品各一个。

此后，该产物可能会作为其他物品配方中的成分。这就是该合成系统如此丰富且具有多层次的原因！为了确保不存在无法合成的配方，题目保证任何物品配方中的所有成分的 ID 编号都始终大于最终产物的 ID 编号。

保证前 $n$ 个物品不会包含在任何其他物品的配方中。我们称这些为传奇最终产物。游戏的目标是尽可能多地制作出不同的传奇最终产物（即多次制作同一种传奇最终产物在计分时只算作一次）。

假设你能够获得一定数量的原材料，而没有其他物品。可以制作出的不同种类传奇最终产物的最大数量是多少？

输入格式

输入的第一行包含两个由空格分隔的整数 $n$ 和 $m$。

接下来的 $m$ 行，每行代表一个物品。第 $i$ 行描述内部 ID 为 $i$ 的物品，以一个整数 $c_i$ 开头，后跟一个空格。

• 如果 $c_i = 0$，则该物品为原材料。随后是一个整数 $p_i$，表示你拥有的该材料数量。
• 否则，如果 $c_i > 0$，则随后有 $c_i$ 个由空格分隔的整数，列出了该物品配方中成分的 ID。

传奇最终产物始终是前 $n$ 个物品。

数据范围

• $1 \le n \le 15$
• 原材料（$c_i = 0$ 的物品）最多有 10 种。
• $n < m \le 2 \cdot 10^5$
• $0 \le c_i \le 2 \cdot 10^5$，且所有物品 $i$ 的 $c_i$ 之和不超过 $5 \cdot 10^5$。
• 对于每种原材料，$0 \le p_i \le 10^8$
• 对于每个传奇最终产物（即 $1 \le i \le n$），$c_i > 0$
• 每个配方由不同的成分组成。
• 对于第 $i$ 个物品的配方（如果有），其所有成分的 ID 均严格大于 $i$ 且大于 $n$。
• 所有 ID 均在 $1$ 到 $m$ 之间（含边界）。

输出格式

输出一个整数，表示可以制作出的不同最终产物的最大数量。

样例

输入 1

2 6
2 3 4
3 4 5 6
0 1
0 1
0 1
0 1

输出 1

1

输入 2

2 6
2 3 4
3 4 5 6
0 1
0 2
0 1
0 1

输出 2

2

输入 3

1 5
2 2 3
2 3 4
2 4 5
0 3
0 2

输出 3

1

输入 4

1 4
3 2 3 4
0 2
1 4
0 1

输出 4

0

说明

在第一个样例测试中，有两个最终产物：一个的配方需要物品 3 和 4，另一个的配方需要物品 4、5 和 6。我们可以制作其中一个，但不能同时制作两个，因此答案为 1。

第二个样例测试与第一个类似，不同之处在于我们有两个物品 4。这使我们能够制作出两个传奇最终产物，因此答案为 2。

在第三个样例测试中，我们需要执行以下操作：

• 制作两个物品 3。
• 制作一个物品 2。这会消耗剩余的物品 4，以及我们刚刚制作的其中一个物品 3。
• 我们拥有一个物品 2 和一个物品 3，因此我们可以用它们来制作物品 1。