4147: 「HEOI2015」兔子与樱花

很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由 $n$ 个树枝分叉点组成，编号从 $0$ 到 $n-1$，这 $n$ 个分叉点由 $n-1$ 个树枝连接，我们可以把它看成一个有根树结构，其中 $0$ 号节点是根节点。这个树的每个节点上都会有一些樱花，其中第 $i$ 个节点有 $c_i$ 朵樱花。樱花树的每一个节点都有最大的载重 $m$，对于每一个节点 $i$，它的儿子节点的个数和 $i$ 节点上樱花个数之和不能超过 $m$，即 $\text{son}(i) + c_i \leq m$，其中 $\text{son}(i)$ 表示 $i$ 的儿子的个数，如果 $i$ 为叶子节点，则 $\text{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