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

Oamenii beau foarte multa bere in Romania. Pentru fiecare oras $i$ din cele $N$ orase ale tarii (numerotate de la $1$ la $N$) se cunoaste cantitatea de bere $B{~i~}$ ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze $K$ berarii in $K$ orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste $2$ orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras $i$ si o berarie amplasata intr-un oras $X$, care este cea mai apropiata berarie de $X$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, unde $dist(i,X)$ este distanta dintre orasul $i$ si orasul $X$. Compania producatoare de bere doreste sa aleaga amplasarea celor $K$ berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.

Oamenii beau foarte multa bere in Romania. Pentru fiecare oras $i$ din cele $N$ orase ale tarii (numerotate de la $1$ la $N$) se cunoaste cantitatea de bere $B{~i~}$ ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze $K$ berarii in $K$ orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste $2$ orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras $i$ si o berarie amplasata intr-un oras $X$, care este cea mai apropiata berarie de $i$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, unde $dist(i,X)$ este distanta dintre orasul $i$ si orasul $X$. Compania producatoare de bere doreste sa aleaga amplasarea celor $K$ berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.

h2. Date de intrare

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

2176