Hide

Problem D
Collapse

/problems/collapse/file/statement/en/img-0001.jpg
Photo by Paul Buckingham
Trouble has come to the remote group of islands known as Insumulia. Due to an unfortunate combination of over-consumption, natural climate variations, and generally difficult conditions, the island of Incunabula has run out of trees. Because several other Insumulian islands depended on trees from Incunabula through trade, its collapse will have repercussions all over Insumulia. In this problem, we’ll simulate a (highly oversimplified) model of the situation to determine the effects of the collapse of Incunabula.

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.

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

Please log in to submit a solution to this problem

Log in