== 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 unui personaj ca fiind egala cu suma din $distanta * viteza$ pentru fiecare cararuie parcursa de acel personaj. Personajele fantastice vor sa gasesti suma maxima a energiilor magice pe care o pot obtine parcurgand padurea. 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

h2. Date de ieşire

În fişierul de ieşire $drumetii.out$ trebuie sa afisati energia magica maxima ce poate fi obtinuta de cele $N$ personaje.

În fişierul de ieşire $drumetii.out$ trebuie sa afisati energia magica maxima ce poate fi obtinuta.

h2. Restricţii