Once upon a time, a group of rabbits lived in a forest. One day, the rabbits decided to go see the cherry blossoms. The cherry blossom tree in the forest is quite special. It consists of $n$ branch nodes, numbered from $0$ to $n-1$, connected by $n-1$ branches. We can view this as a rooted tree structure, where node $0$ is the root. Each node in the tree has some cherry blossoms, with the $i$-th node having $c_i$ cherry blossoms. Every node in the cherry blossom tree has a maximum load capacity $m$. For each node $i$, the sum of the number of its children and the number of cherry blossoms at node $i$ must not exceed $m$, i.e., $\text{son}(i) + c_i \le m$, where $\text{son}(i)$ represents the number of children of $i$. If $i$ is a leaf node, then $\text{son}(i) = 0$.

Now, the rabbits feel that there are too many nodes in the cherry blossom tree and wish to remove some of them. When a node is removed, the cherry blossoms on this node and its children are all connected to the parent of the removed node. If the parent is also removed, this connection continues upward until the first node that has not been removed is reached.

The rabbits want to calculate the maximum number of nodes that can be removed without violating the maximum load capacity. Note that the root node cannot be removed, and removed nodes are not counted towards the load.

Input

The first line contains two positive integers, $n$ and $m$, representing the number of nodes and the maximum load capacity, respectively.

The second line contains $n$ integers $c_i$, representing the number of cherry blossoms at the $i$-th node.

The next $n$ lines each contain the number of children $k_i$ for that node, followed by $k_i$ integers representing the indices of the children of that node.

Output

Output a single integer representing the maximum number of nodes that can be removed.

Examples

Input 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

Output 1

4

Constraints

For 30% of the data, $1 \le n \le 5000$, $1 \le m \le 100$, $0 \le c_i \le 100$.

For 70% of the data, $1 \le n \le 200000$, $1 \le m \le 2000$, $0 \le c_i \le 1000$.

For 100% of the data, $1 \le n \le 2000000$, $1 \le m \le 100000$, $0 \le c_i \le 1000$.

The data guarantees that initially, the sum of the number of cherry blossoms and the number of children for each node is greater than $0$ and does not exceed $m$.