You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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$$$.

## Examples
```input
6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5
```
```output
4
```
-----
```input
6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5
```
```output
10
```
-----
```input
2 1 5
1 1
1 2
```
```output
-1
```
-----
```input
1 0 1
1000000000
```
```output
1000000000
```

## Note
Graph described in the first and the second examples is illustrated below.

In the first example Masha can initially put a coin at vertex $$$1$$$. After that she can perform three operations: $$$1 \to 3$$$, $$$3 \to 4$$$ and $$$4 \to 5$$$. Integers $$$1, 2, 3$$$ and $$$4$$$ will be written in the notepad.

In the second example Masha can initially put a coin at vertex $$$2$$$. After that she can perform $$$99$$$ operations: $$$2 \to 5$$$, $$$5 \to 6$$$, $$$6 \to 2$$$, $$$2 \to 5$$$, and so on. Integers $$$10, 4, 5, 10, 4, 5, \ldots, 10, 4, 5, 10$$$ will be written in the notepad.

In the third example Masha won't be able to perform $$$4$$$ operations.

Now solve the problem and return the code.