== include(page="template/taskheader" task_id="lianyu") ==
Pe insula Lian Yu sunt $N$ asezari conectate prin $M$ drumuri bidirectionale. Pe aceasta insula renumitul Slade Wilson creste cel mai periculos drog si de asemena cea mai periculoasa arma, Mirakuru. A.R.G.U.S a aflat de aceasta operatiune si vrea sa trimita $K$ echipaje de soldati sa investigheze si sa obtina informatii esentiale. Totusi acest lucru nu este chiar atat de simplu si prin urmare A.R.G.U.S v-a angajat pe voi trei sa le spuneti costul minim pentru a trimite $K$ echpaje de soldati pe insula tinand cont de urmatoarele conditii:
Pe insula Lian Yu sunt $N$ asezari, numerotate de la $1$ la $N$, conectate prin $M$ drumuri bidirectionale. Pe aceasta insula renumitul Slade Wilson creste cel mai periculos drog si de asemena cea mai periculoasa arma, Mirakuru. A.R.G.U.S a aflat de aceasta operatiune si vrea sa trimita $K$ echipaje de soldati sa investigheze si sa obtina informatii esentiale. Totusi acest lucru nu este chiar atat de simplu si prin urmare A.R.G.U.S v-a angajat pe voi trei sa le spuneti costul minim pentru a trimite $K$ echpaje de soldati pe insula tinand cont de urmatoarele conditii:
* datorita structurii insulei, in fiecare asezare $i$ poate fi lasat, de catre avioane, maxim un echipaj de soldati cu costul cost[i]
* dupa aterizarea echipajelor acestia vor trebui sa se intalneasca intr-o asezare ca sa continue planul. Datorita interventiei bruste a echipajului si a suportului aerian, soldatii vor putea elimina toti mercenarii lui Slade Wilson care se vor afla in asezarile unde vor ateriza acestia De indata ce soldatii vor ateriza, se va da alarma in toata insula si toti mercenarii vor lua cat mai mult Mirakuru si se vor aduna intr-una din asezari ca sa-l protejeze (si cel mai probabil daca soldatii vor trece prin aceasta asezare vor fi omorati, cea ce este totatl exclus).
Asadar echipajele trebuie lasate in asezari astfel incat in orcicare din cele ramase s-ar strange mercenarii lui Slade Wilson, soldatii sa poata sa se stranga intr-o asezare fara sa treaca prin cea aleasa de de Slade Wilson si echipa sa.
* datorita structurii insulei, in fiecare asezare $i$ poate fi lasat, de catre avioane, maxim un echipaj de soldati cu costul $cost[~i~]$.
* dupa aterizarea echipajelor acestea vor trebui sa se intalneasca intr-o asezare ca sa continue planul. Datorita interventiei bruste a echipajului si a suportului aerian, soldatii vor putea elimina toti mercenarii lui Slade Wilson care se vor afla in asezarile unde vor ateriza acestia. De indata ce soldatii vor ateriza, se va da alarma in toata insula si toti mercenarii vor lua cat mai mult Mirakuru si se vor aduna intr-una din asezari ca sa-l protejeze (si cel mai probabil daca soldatii vor trece prin aceasta asezare vor fi omorati, cea ce este total exclus).
Asadar echipajele trebuie lasate in asezari astfel incat in oricare din cele ramase s-ar strange mercenarii lui Slade Wilson, soldatii sa poata sa se intalneasca intr-o asezare fara sa treaca prin cea aleasa de de Slade Wilson si echipa sa.
h2. Date de intrare
Fişierul de intrare $lianyu.in$ contine pe prima linie trei numere naturale $N$ (numarul de asezari), $M$ (numarul de drumuri) si $K$ (numarul de echipaje ce trebuie trimise).
Fişierul de intrare $lianyu.in$ contine pe prima linie trei numere naturale $N$ (numarul de asezari), $M$ (numarul de drumuri) si $K$ (numarul de echipaje ce trebuie trimise). Pe urmatoarea linie se afla $N$ numere naturale despartite printr-un spatiu, al $i$-lea fiind $cost[~i~]$. Pe urmatoarele $M$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista un drum bidirectional intre asezarile $x$ si $y$.
h2. Date de ieşire
În fişierul de ieşire $lianyu.out$ ...
În fişierul de ieşire $lianyu.out$ se va afisa un singur numar natural reprezentand costul minim pentru a trimite $K$ echipaje pe insula cu restrictiile de mai sus.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 3000$
* $1 ≤ M ≤ 5000$
* $1 ≤ cost[~i~] ≤ 10^5^$
* $Se poate ajunge de la oricare asezare la oricare alta mergand pe cele $M$ drumuri$
* $Intre oricare doua asezari exista maxim un drum si nu exista drum de la o asezare la ea insasi$
h2. Exemplu
table(example). |_. lianyu.in |_. lianyu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5 2
2 4 1 4 1
1 2
2 3
3 4
1 4
4 5
| 3
|
h3. Explicaţie
...
Se trimit echipaje in asezarile 1 si 3.
Un cost mai bun se poate obtine daca am trimite echipaje in asezarile 3 si 5, dar daca mercenarii se vor strange in asezarea 4 atunci echipajul din asezarea 5 nu se va mai putea intalni cu cel din asezarea 3.
== include(page="template/taskfooter" task_id="lianyu") ==
