h2. Date de intrare

Pe prima linie a fişierului de intrare autostrazi.in se află trei numere întregi $N$, $S$ si $K$ separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află $K$ numere naturale, $R1, R2, .. Rk$, nu neapărat distincte, separate printr-un singur spaţiu, reprezentând taxele percepute de regii asfaltului. Pe următoarele $N – 1$ linii se găsesc câte două numere naturale distincte $x$ şi $y$ separate printr-un singur spaţiu

Pe prima linie a fişierului de intrare autostrazi.in se află trei numere întregi $N$, $S$ si $K$ separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află $K$ numere naturale, $R{~1~}, R{~2~}, .. R{~k~}$, nu neapărat distincte, separate printr-un singur spaţiu, reprezentând taxele percepute de regii asfaltului. Pe următoarele $N – 1$ linii se găsesc câte două numere naturale distincte $x$ şi $y$ separate printr-un singur spaţiu

reprezentând o şosea care leagă oraşul $x$ de oraşul $y$.

* $1 ≤ x, y ≤ N ≤ 100$
* $1 ≤ K ≤ 20$
* $1 ≤ S ≤ 100$

* $1 ≤ R1, R2, .. Rk ≤ 100$
* Regele $i$ al asfaltului impune aceeaşi taxă $Ri$ pentru fiecare autostradă constuită de el şi poate construi zero, una sau maxim $N – 1$ autostrăzi.

* $1 ≤ R{~1~}, R{~2~}, .. R{~k~} ≤ 100$
* Regele $i$ al asfaltului impune aceeaşi taxă $R{~i~}$ pentru fiecare autostradă constuită de el şi poate construi zero, una sau maxim $N – 1$ autostrăzi.

* O şosea se concesionează în întregime unui singur constructor sau poate să nu fie concesionată deloc. În acest caz nu există taxă de trecere.
* Este admis cazul în care nu se concesionează nicio şosea.