team

Team

== include(page="template/taskheader" task_id="team") ==

Sambata o petrec cu prietenii la discoteca "Why not" din centrul orasului. De acolo plecam in zori $p $ persoane, in gasca, si trebuie sa ajungem fiecare acasa. Atat la discoteca, la punctele de destinatie ale membrilor gastii, precum si in alte puncte ale orasului se afla statii de Team-Taxi pe care le putem folosi �®n drumul spre casa, platind frateste pe fiecare segment de drum o suma fixa pe care o pretinde soferul masinii (in functie de lungimea drumului si nu in functie de numarul de pasageri). In orice statie pot parasi gaaca numai cei care au ajuns la destinatie, in acest caz grupurile omogene formate urmand sa se desparta (pentru ca au disp��rut oamenii de legatura) si sa ia in continuare taxiuri cu diferite destinatii. Doua grupuri omogene diferite pot merge �®n aceeasi destinatie, dar utilizand taxiuri diferite. Numim grup omogen o formatie de persoane cu numere de ordine consecutive. De exemplu, pentru $p=6$, de la discoteca porne��te gasca in formatia $1 2 3 4 5 6$. Daca la o statie se opreste persoana num��rul $3$, atunci se formeaz�� doua grupuri omogene, $1 2$  si $4 5 6$. Ei se despart luand doua taxiuri diferite. Doua grupe formate din $1 4 5$ ��i $2 6$ nu sunt omogene.
Atata timp cat $k$ persoane merg cu un taxi pe un segment pe care orice sofer cere invariabil suma $c$, contributia fiecaruia pe acel segment este $c/k$. Dac�� o persoana merge singura cu un taxi pe segmentul respectiv, ea va trebui s�� plateasca singura intreaga suma.

Sambata o petrec cu prietenii la discoteca "Why not" din centrul orasului. De acolo plecam in zori $p$ persoane, in gasca, si trebuie sa ajungem fiecare acasa. Atat la discoteca, la punctele de destinatie ale membrilor gastii, precum si in alte puncte ale orasului se afla statii de Team-Taxi pe care le putem folosi in drumul spre casa, platind frateste pe fiecare segment de drum o suma fixa pe care o pretinde soferul masinii (in functie de lungimea drumului si nu in functie de numarul de pasageri). In orice statie pot parasi gasca numai cei care au ajuns la destinatie, in acest caz grupurile omogene formate urmand sa se desparta (pentru ca au disparut oamenii de legatura) si sa ia in continuare taxiuri cu diferite destinatii. Doua grupuri omogene diferite pot merge in aceeasi destinatie, dar utilizand taxiuri diferite. Numim grup omogen o formatie de persoane cu numere de ordine consecutive. De exemplu, pentru $p=6$, de la discoteca porneste gasca in formatia $1 2 3 4 5 6$. Daca la o statie se opreste persoana numarul $3$, atunci se formeaza doua grupuri omogene $1 2$ si $4 5 6$. Ei se despart luand doua taxiuri diferite. Doua grupe formate din $1 4 5$ si $2 6$ nu sunt omogene. Atata timp cat $k$ persoane merg cu un taxi pe un segment pe care orice sofer cere invariabil suma $c$, contributia fiecaruia pe acel segment este $c/k$. Daca o persoana merge singura cu un taxi pe segmentul respectiv, ea va trebui sa plateasca singura intreaga suma.

h2. Cerinta

* $p$ numarul de persoane din gasca ce pleaca de la discoteca, de pe linia $1$
* $n$ numarul de statii de taxi din oras, de pe linia $2$; statiile sunt numerotate de la $1$ la $n$
* $m$ numarul de segmente ce leaga direct cate doua statii, de pe linia $3$

* $m$ triplete de forma $i j c$ ($i$ si $j$ sunt statiile intre care se considera segmentul, iar $c$ costul de transport pe segmentul respectiv), de pe urm��toarele $m$ linii
* $d{~1~} d{~2~} � d{~p~}$ statiile de destinatie ale membrilor gastii (nu neaparat distincte), de pe ultima linie.

* $m$ triplete de forma $i j c$  ( $i$ si $j$ sunt statiile intre care se considera segmentul, iar $c$ costul de transport pe segmentul respectiv), de pe urmatoarele $m$ linii
* $d{~1~} d{~2~} ... d{~p~}$ statiile de destinatie ale membrilor gastii (nu neaparat distincte), de pe ultima linie.

h2. Date de iesire

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ p ≤ 50$
* $2 ≤ n ≤ 500$
* $1 ≤ i, j ≤ n$
* $0 ≤ c ≤ 1000$
* $1 ≤ d{~1~}, d{~2~} ... d{~p~} ≤ n$
* se considera statia $1$ ca punct de plecare (discoteca)
* pe toate strazile se poate circula in ambele sensuri
* pentru datele de test exista intotdeauna solutie
* toate datele de intrare sunt numere naturale

h2. Exemplu
table(example). |_. team.in |_. team.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
  5
  8
  1 2 6
  1 3 4
  3 4 8
  2 4 1
  3 5 7
  2 3 1
  1 5 6
  2 5 0
  5 2 4 4
| 6

|

h3. Explicatie

== include(page="template/taskfooter" task_id="team") ==
 

...
== include(page="template/taskfooter" task_id="team") ==

1712