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, $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

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$.
h2. Date de ieşire

În fişierul de ieşire autostrazi.out se află un singur număr natural $M$, reprezentând numărul de posibilităţi modulo $30011$ în care poate fi construită reţeaua de autostrăzi, astfel încat suma taxelor plătite într-o călătorie între oricare două oraşe să nu depăşească $S$ euro.

În fişierul de ieşire $autostrazi.out$ se află un singur număr natural $M$, reprezentând numărul de posibilităţi modulo $30011$ în care poate fi construită reţeaua de autostrăzi, astfel încat suma taxelor plătite într-o călătorie între oricare două oraşe să nu depăşească $S$ euro.

h2. Restricţii şi precizări