== 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!). 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 $N$ 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 $N-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!). 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$.

h2. Date de intrare

Fişierul de intrare $drumetii.in$ va contine pe prima linia numarul $N$ reprezentand numarul de personaje fantastice. Pe a doua linie din input se vor gasi $N$ numere $V{~1~},V{~2~}...V{~N~}$ reprezentand vitezele de deplasare ale celor $N$ personaje. A treia linie din input va contine numerul $P$ reprezentand numarul de luminisuri. Pe fiecare dintre liniile de la $4$ la $4+P-2$ se va gasi cate o pereche de numere $X,Y,L$ reprezentand faptul ca exista o carare de la $X$ la $Y$ de lungime $L$.

Fişierul de intrare $drumetii.in$ va contine pe prima linia numarul $N$ reprezentand numarul de personaje fantastice. Pe a doua linie din input se vor gasi $N$ numere $V{~1~},V{~2~}...V{~N~}$ reprezentand vitezele de deplasare ale celor $N$ personaje. Pe fiecare dintre liniile de la $3$ la $3+N-2$ se va gasi cate o pereche de numere $X,Y,L$ cu semnificatia ca exista o cararuie de la $X$ la $Y$ de lungime $L$.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 15$
* $1 ≤ P ≤ 1000$
* $1 ≤ L ≤ 1000$

* $1 ≤ N ≤ 20$
* $1 ≤ L ≤ 100 000$
* $1 ≤ V{~i~} ≤ 1000$

* Se garanteaza ca se poate ajunge din nodul $1$ in orice alt nod al padurii.
* O muchie poate fi parcursa in ambele sensuri.
* Un personaj nu are voie sa astepte intre-un poiana. Cu alte cuvinte, cazul in care doua personaje sunt in acelasi nod si aleg ambele sa mearga pe aceeasi cararuie, primul personaj merge iar al doilea astepta si merge dupa acesta este invalid.