## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Toss a Coin to Your Graph... Codeforces Solution | Codeforces Problem Solution 2022

D. Toss a Coin to Your Graph...
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day Masha was walking in the park and found a graph under a tree... Surprised? Did you think that this problem would have some logical and reasoned story? No way! So, the problem...

Masha has an oriented graph which $i$-th vertex contains some positive integer ${a}_{i}$. Initially Masha can put a coin at some vertex. In one operation she can move a coin placed in some vertex $u$ to any other vertex $v$ such that there is an oriented edge $u\to v$ in the graph. Each time when the coin is placed in some vertex $i$, Masha write down an integer ${a}_{i}$ in her notebook (in particular, when Masha initially puts a coin at

some vertex, she writes an integer written at this vertex in her notebook). Masha wants to make exactly $k-1$ operations in such way that the maximum number written in her notebook is as small as possible.

Input

The first line contains three integers $n$$m$ and $k$ ($1\le n\le 2\cdot {10}^{5}$$0\le m\le 2\cdot {10}^{5}$$1\le k\le {10}^{18}$) — the number of vertices and edges in the graph, and the number of operation that Masha should make.

The second line contains $n$ integers ${a}_{i}$ ($1\le {a}_{i}\le {10}^{9}$) — the numbers written in graph vertices.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1\le u\ne v\le n$) — it means that there is an edge $u\to v$ in the graph.

It's guaranteed that graph doesn't contain loops and multi-edges.

Output

Print one integer — the minimum value of the maximum number that Masha wrote in her notebook during optimal coin movements.

If Masha won't be able to perform $k-1$ operations, print $-1$.