Problem F
Hopeful Sleep Prevention Analysis
Languages
en
sv
snabbare uppkoppling desto lyckligare är användarna. För 4G eller LTE nät beror hastigheten/bandbredden på hur många som använder nätet i ett område samtidigt vilket gör att efter en viss punkt börjar nätet sega så att man somnar. En av fördelarna med 5G att man skulle kunna öka kapaciteten för antalet uppkopplade enheter avsevärt mycket men tills dess vill Ericsson gärna veta hur många som klarar av att använda nätet utan att de somnar.
Antag nu att alla användare lägger lika stor belastning på
bandbredden, 1 $\delta $
var och att alla master är
indexerade mellan $1$ och
$k$. Varje mast har en
viss
kapacitet för antalet $\delta
$ som kan gå igenom den innan alla somnar. En del master
är dessutom kopplade till stamnätet. Stamnätet har en kapacitet
som är oändlig i jämförelse med masterna och indexeras som mast
0. När en användare kopplar sig till en mast måste
informationen gå hela vägen till stamnätet för att användaren
ska kunna betjänas. Eftersom att hastighet är viktigt är
användarna garanterade att de blir kopplade till högst de tre
närmaste masterna för att minimera distansen signalen måste
skickas i luften.
Ericsson vill nu att du, givet masternas kopplingar och deras kapacitet i $\delta $, tar reda på hur många användare som kan använda nätverket samtidigt utan att somna.
Indata
På första raden kommer två tal $n$ och $k$, antalet användare och antalet eNode-master. Efter det kommer det $k$ rader, en för varje mast exlusive stamnätet, med ett tal $c_ i$, kapaciteten för masten och ett tal $m_ i$ som representerar antalet master som mast nummer $i$ är kopplad till. Därefter kommer $m_ i$ tal på samma rad, index för masterna som mast nummer $i$ är kopplade till. Därefter följer ytterligare $k$ rader med ett tal $p_ i$, antalet användare som är inom respektive masts räckvidd och $p_ i$ tal som är index för användarna.
$1 \leq n \leq 5000,\, \quad 2
\leq k \leq 100$
$1 \leq c_ i \leq 5000,\quad 1
\leq m_ i < k$
Utdata
Utdata är ett tal, det maximala antalet personer som kan använda nätverket utan att somna.
| 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 |
