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

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de $N$ puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu nr 1 care este langa scoala sa, pana la barul $N$, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta $K$, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina $K$ la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de $N$ puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu numarul 1 care este langa scoala sa, pana la barul $N$, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta $K$, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina $K$ la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

h2. Date de intrare

Fişierul de intrare $pesaptecarari.in$ va contine pe prima linie. $3$ numere $N$, $M$, $K$ corespunzand numarului de baruri, numarului strazilor ce leaga baruri intre ele, respectic coeficientul de siguranta $K$. Urmatoarea linie contine $N$ valori, $A[~i~]$ corespunzand indicelui alcoolic pt fiecare pub din cele $N$. Urmatoarele $M$ linii contin cate $2$ numere: $x$ $y$ aratand ca exista un drum cu sens unic de la $x$ la $y$.

Fişierul de intrare $pesaptecarari.in$ va contine pe prima linie $3$ numere $N$, $M$, $K$ reprezentand numarul de baruri, numarul strazilor ce leaga baruri intre ele, respectiv coeficientul de siguranta $K$. Urmatoarea linie contine $N$ valori, $A[~i~]$ reprezentand indicele alcoolic pentru fiecare pub din cele $N$. Urmatoarele $M$ linii contin cate $2$ numere: $x$, $y$ aratand ca exista un drum cu sens unic de la $x$ la $y$.

h2. Date de ieşire

Fişierul de ieşire $pesaptecarari.out$ va contine pe prima linie puterea minima la care apare $K$ in produsul indicilor alcoolici pentru un puburile de pe un drum optim.

Fişierul de ieşire $pesaptecarari.out$ va contine pe prima linie puterea minima la care apare $K$ in produsul indicilor alcoolici pentru drumul optim intre barul $1$ si $N$.

Pe urmatoarea linie se va afisa un drum de la barul $1$ la barul $N$.
h2. Restricţii