Problem C
Collapse

Photo by Paul Buckingham

We model the situation as follows. Each island has a threshold $T_ i$ on the amount of incoming goods (for simplicity we assume that there is only a single commodity of goods) it needs to receive per lunar cycle in order for the society of the island to sustain itself. If the amount of incoming goods drops below the threshold, society on the island will collapse and die out, and the island will no longer provide goods to other islands, thereby potentially causing them to collapse as well. Each island provides some amount of goods to a number of other islands. If an island collapses, we assume that goods that would have been delivered to that island is effectively lost; it does not get redistributed and delivered to other islands instead. Also, once an island dies out it is not repopulated (until possibly long after the ongoing collapses have finished).

Your job is to write a program to compute the number of islands that survive after the potential chain reaction of collapses that is caused by the collapse of Incunabula.

Input

The first line of input contains an integer $N$ ($1 \le N \le 100\, 000$), the number of islands in Insumulia.

Then follow $N$ lines, describing each island. The $i$’th such description starts with two integers $T_ i$, $K_ i$, where $0 \le T_ i \le 50\, 000$ is the amount of goods the $i$’th island needs to receive in order to survive, and $0 \le K_ i \le N-1$ is the number of other islands the $i$’th islands receives goods from. The remainder of the description of the $i$’th island is a list of $K_ i$ pairs of integers. The $j$’th such pair, $S_{ij}$, $V_{ij}$, indicates that island $i$ receives $V_{ij}$ units of goods from island $S_{ij}$ each lunar cycle. You may assume that the $S_{ij}$’s are distinct and between $1$ and $N$ (inclusive), and that none of them equals $i$. The values $V_{ij}$ satisfy $1 \le V_{ij} \le 1000$ and their sum is at least $T_ i$. The sum of all the $K_ i$’s for all the $N$ islands is at most $500\, 000$.

Islands are numbered from $1$ to $N$, and Incunabula is island number $1$.

Output

Output a single integer, the number of islands surviving the collapses.

4
0 0
25 3 1 10 3 10 4 10
10 1 2 10
10 1 2 10

0

4
0 0
20 3 1 10 3 10 4 10
10 1 2 10
10 1 2 10

3