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.

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 a single integer, the number of islands surviving the collapses.

Sample Input 1 | Sample Output 1 |
---|---|

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

Sample Input 2 | Sample Output 2 |
---|---|

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