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
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 (), the number of islands in
Insumulia.
Then follow lines,
describing each island. The ’th such description starts with
two integers ,
, where is the
amount of goods the ’th
island needs to receive in order to survive, and is the number of
other islands the ’th
islands receives goods from. The remainder of the description
of the ’th island is a
list of pairs of
integers. The ’th such
pair, ,
, indicates that
island receives
units of goods
from island each
lunar cycle. You may assume that the ’s are distinct and between
and (inclusive), and that none of them
equals . The values
satisfy
and their sum is at least . The sum of all the ’s for all the islands is at most .
Islands are numbered from to , and Incunabula is island number
.
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
|
