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

$N$ personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are $P$ luminisuri legate intre ele prin cararui de diferite lungimi. Initial personajele sunt in luminisul $1$. Stim ca oricare doua cararui nu se vor intersecta decat intr-un luminis, si ca numarul total de cararui va fi $P-1$. Fiecare dintre cele $N$ personaje urmeaza urmatoarea strategie de vizitare a padurii: Din luminisul in care se afla acum, alege o cararuie pe care nu a parcurs-o in prealabil, si merge pe aceasta. Deasemenea, daca sunt mai multe personaje in acelasi luminis care vor sa mearga mai departe pe aceeasi cararuie, atunci vor merge ca grup - se vor deplasa pe respectiva cararuie cu viteza celui mai incet dintre ele (calul lui Harap-Alb este mai rapid decat Cenusareasa!). In cazul in care un personaj ajunge intr-un luminis din care nu poate iesi (nu exista cararui nevizitate), atunci acel personaj se va opri. Vom numi un astel de luminis $luminis terminal$. Stim ca in padure exista **cel mult** $N$ luminisuri terminale. Definim energia magica a padurii ca fiind egala cu suma din $distanta * viteza$ pentru fiecare cararuie (daca o cararuie nu va fi parcursa, aceasta suma va fi $0$). Personajele fantastice vor sa gasesti energia magica maxima ce se poate obtine. Daca esti vrednic sa rezolvi aceasta problema vei fi rasplatit cu placeri nebanuite...si $100p$.

$N$ personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are $P$ luminisuri legate intre ele prin cararui de diferite lungimi. Initial personajele sunt in luminisul $1$. Stim ca oricare doua cararui nu se vor intersecta decat intr-un luminis si ca numarul total de cararui va fi $P-1$. Fiecare dintre cele $N$ personaje urmeaza urmatoarea strategie de vizitare a padurii: Din luminisul in care se afla acum, alege o cararuie pe care nu a parcurs-o in prealabil, si merge pe aceasta. Deasemenea, daca sunt mai multe personaje in acelasi luminis care vor sa mearga mai departe pe aceeasi cararuie, atunci vor merge ca grup - se vor deplasa pe respectiva cararuie cu viteza celui mai incet dintre ele (calul lui Harap-Alb este mai rapid decat Cenusareasa!). In cazul in care un personaj ajunge intr-un luminis din care nu poate iesi (nu exista cararui nevizitate), atunci acel personaj se va opri. Vom numi un astel de luminis $luminis terminal$. Stim ca in padure exista **cel mult** $N$ luminisuri terminale. Definim energia magica a padurii ca fiind egala cu suma din $distanta * viteza$ pentru fiecare cararuie (daca o cararuie nu va fi parcursa, aceasta suma va fi $0$). Personajele fantastice vor sa gasesti energia magica maxima ce se poate obtine. Daca esti vrednic sa rezolvi aceasta problema vei fi rasplatit cu placeri nebanuite...si $100p$.

h2. Date de intrare

1 3 10
| 120
|

| 4
81 372 461 987
4
1 2 64270
1 3 56978
3 4 28202
| 89278530
|

h3. Explicaţie

Personajele $1$ si $2$ vor calatori impreuna spre poiana $2$, iar personajul al treilea va calatori singur spre poiana $9$. Primele doua personaje vor parcurge muchia $(1,2)$ cu viteza 3, iar personajul $3$ va parcurge muchia $(1,3)$ cu viteza $9$. Costul total va fi $3*10+9*10=120$.

In primul exemplu, personajele $1$ si $2$ vor calatori impreuna spre poiana $2$, iar personajul al treilea va calatori singur spre poiana $9$. Primele doua personaje vor parcurge muchia $(1,2)$ cu viteza 3, iar personajul $3$ va parcurge muchia $(1,3)$ cu viteza $9$. Costul total va fi $3*10+9*10=120$.

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