După cum spune şi numele problemei, aceasta este o problemă *simplă* cu grafuri. Iar cu ocazia sărbătorilor de iarnă, Moş Crăciun s-a gândit să scurteze enunţul acestei probleme şi să vă premieze cu $100$ puncte dacă o rezolvaţi corect!

Se dă un graf orientat aciclic cu $N$ noduri şi $M$ muchii. Fiecare nod $i$ are o valoare $v[i]$. Se dă un număr natural $K$. Să se găsească şi să se afişeze suma maximă a unui lanţ format din cel mult $K$ noduri distincte. Suma unui lanţ este suma valorilor nodurilor conţinute de acesta.

Se dă un graf orientat aciclic cu $N$ noduri şi $M$ muchii. Fiecare nod $i$ are o valoare $v[i]$. Să se găsească şi să se afişeze suma maximă a unui lanţ din graf. Suma unui lanţ este suma valorilor nodurilor conţinute de acesta.

h2. Date de intrare

Fişierul de intrare $easygraph.in$ conţine pe prima linie numărul de teste, $T$. În continuare, pentru fiecare test, se vor găsi pe prima linie trei numere naturale, $N$, $M$ şi $K$, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi $N$ numere naturale, elementele vectorului $v[i]$. Pe următoarele $M$ linii se vor găsi câte două numere $x$ şi $y$, cu semnificaţia că există o muchie orientată de la nodul $x$ la nodul $y$.

Fişierul de intrare $easygraph.in$ conţine pe prima linie numărul de teste, $T$. În continuare, pentru fiecare test, se vor găsi pe prima linie două numere naturale $N$ şi $M$, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi $N$ numere naturale, elementele vectorului $v[i]$. Pe următoarele $M$ linii se vor găsi câte două numere $x$ şi $y$, cu semnificaţia că există o muchie orientată de la nodul $x$ la nodul $y$.

h2. Date de ieşire