[HEOI2015]兔子与樱花

题目描述

很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。 兔子们所在森林里的樱花树很特殊。樱花树由 $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$ 个整数表示这个节点儿子的编号。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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$。