Problem F
Hopeful Sleep Prevention Analysis
Languages
en
sv
Let us assume that every user puts the same burden on the
network one $\delta $ each
and that every mast is indexed between $1$ and $k$. Each mast has a certain capacity
of number of $\delta $
that can go through the mast before
everyone falls asleep. Additionally some masts are
connected to the backbone network. The backbone
network has an infinitely large capacity compared to the
network masts and is indexed as mast $0$. When a user connects to a mast
the information must go all the way to the backbone network for
the user to be served. Also, since speed is important the users
are guaranteed to be able to connect to at most the three
closest masts to minimize the distance the signal must travel
through the air.
Ericsson would now like you, given the masts connections between eachother and their capacity in $\delta $, to assess how many users can be connected to the network simultaneously without falling asleep.
Input
The first row contains two numbers $n$ and $k$, the number of users and the number of network masts. The following $k$ rows, one for each mast not including the backbone network, contains the integers $c_ i$ and $m_ i$ representing the capacity for the mast and the number of masts that mast $i$ is connected to. Directly after follows $m_ i$ numbers on the same row, the indexes of the connected masts. Then follows another $k$ rows with a integer $p_ i$, the number of users that are in range and $p_ i$ numbers representing the users index $1$ to $n$.
$1 \leq n \leq 5000,\quad 2
\leq k \leq 100$
$1 \leq c_ i \leq 5000,\quad 1
\leq m_ i < k$
Output
Output is a number, the maximum number of users that can be connected simoultaneously without falling asleep.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 4 3 1 0 5 1 3 7 3 0 2 4 5 1 3 1 6 5 5 7 3 10 2 4 3 8 5 4 6 9 10 2 3 1 6 |
8 |
