题目描述

很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。

兔子们所在森林里的樱花树很特殊。樱花树由 $n$ 个树枝分叉点组成，编号从 $0$ 到 $n-1$，这 $n$ 个分叉点由 $n-1$ 个树枝连接，我们可以把它看成一个有根树结构，其中 $0$ 号节点是根节点。

这个树的每个节点上都会有一些樱花，其中第 $i$ 个节点有 $c_i$ 朵樱花。樱花树的每一个节点都有最大的载重 $m$，对于每一个节点 $i$，它的儿子节点的个数和 $i$ 节点上樱花个数之和不能超过 $m$，即 $son(i) + c_i \leq m$，其中 $son(i)$ 表示 $i$ 的儿子的个数，如果 $i$ 为叶子节点，则 $son(i) = 0$。

现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。

现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。

注意根节点不能被删除，被删除的节点不被计入载重。

输入格式

第一行输入两个正整数，$n$ 和 $m$ 分别表示节点个数和最大载重。

第二行 $n$ 个整数 $c_i$，表示第 $i$ 个节点上的樱花个数。

接下来 $n$ 行，每行第一个数 $k_i$ 表示这个节点的儿子个数，接下来 $k_i$ 个整数表示这个节点儿子的编号。

输出格式

一行一个整数，表示最多能删除多少节点。

10 4
0 2 2 2 4 1 0 4 1 1
3 6 2 3
1 9
1 8
1 1
0
0
2 7 4
0
1 5
0

4

提示

• 对于 $30\%$ 的数据，$n \leq 5 \times 10^3$，$m \leq 100$，$c_i \leq 100$；
• 对于 $70\%$ 的数据，$n \leq 2 \times 10^5$，$m \leq 2 \times 10^3$，$c_i \leq 10^3$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^6$，$1 \leq m \leq 10^5$，$0 \leq c_i \leq 10^3$，保证初始时，每个节点樱花数与儿子节点个数之和大于 $0$ 且不超过 $m$。