Problem E
Byteshandel
Vi har alla hört den fascinerande berättelsen om hur någon lyckades byta ett gem mot en penna, sedan byta pennan mot ett dörrhandtag och så vidare, ända tills han bytte sig hela vägen till ett hus. I dagens bostadsmarknad tycker du att detta låter som en lysande idé och tänker försöka dig på något liknande.
Efter att ha analyserat marknaden har du kommit fram till att det finns $N$ stycken olika föremål och $M$ stycken möjliga byten. Ett byte består av en mängd föremål som du kan byta mot exakt ett av ett annat föremål. Exempelvis skulle ett byte kunna vara 2 äpplen och 3 päron mot en apelsin. Formellt kan man beskriva ett byte som
\[ C_{i,0} \cdot F_0 + C_{i,1} \cdot F_1 + \dots + C_{i,N-1} \cdot F_{N-1} \implies 1 \cdot F_{r_i}. \]Här representerar $C_{i,j}$ koefficienten för $F_j$ i byte $i$. Alltså innebär $C_{i,j}$ antalet $F_j$ man behöver för att utföra detta bytet. $r_i$ är det föremål som du får som resultat av byte $i$. Observera att alla föremål inte behöver ingå i ett visst byte; för dessa föremål är $C_{i,j} = 0$.
Varje byte kan utföras valfritt antal gånger. Ditt mål är att beräkna hur många gem som behövs för att få ett hus.
Föremålet $F_0$ representerar gemet, och föremålet $F_{N-1}$ representerar huset.
Indata
Den första raden innehåller två heltal $N$ och $M$ ($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$), antalet föremål och antalet byten.
Därefter beskrivs de $M$ bytena. Varje beskrivning börjar med två heltal $r_i$ ($0 \leq r_i < N$) och $k_i$ ($1 \leq k_i \leq N$), där $r_i$ är föremålet man får av byte $i$, och $k_i$ är antalet olika föremål som används i bytet. Därefter följer $k_i$ rader, där varje rad innehåller två heltal $C_{i,j}$ ($1 \leq C_{i,j} \leq 100$) och $j$ ($0 \leq j < N$), som anger att koefficienten $C_{i,j}$ hör till föremålet $F_j$ i bytet. Notera att föremål med koefficient $0$ inte finns med i indatan.
Låt $K$ vara summan av $k_i$ över alla byten. Det gäller att $K \leq 10^5$.
Det är garanterat att det går att få tag på alla föremål genom att bara starta med gem och man kan köpa varje föremål för som mest $10^9$ gem vardera.
Utdata
Skriv ut ett heltal: det minsta antalet gem som krävs för att du ska kunna byta dig till ett hus.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$12$ |
$N = 3$ |
|
$2$ |
$10$ |
$k_i = 1$ |
|
$3$ |
$25$ |
Det finns en ordning av föremålen så att för varje föremål $f$, så innehåller alla byten där man får $f$ endast föremål som kommer tidigare i ordningen än $f$. |
|
$4$ |
$26$ |
$K \leq 1000$ |
|
$5$ |
$27$ |
Inga ytterligare begränsningar. |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 1 1 5 1 2 1 2 0 1 2 2 0 1 2 3 2 1 1 1 2 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 1 1 7 0 2 1 8 1 |
56 |
