M. Magic labyrinth
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's an explorer entering a magic labyrinth. As he enters, the entrance closes behind him and the labyrinth starts filling up with poisonous gas. Once he realises, he asks for your help so that he is exposed to the minimum amount of gas possible.

The labyrinth can be represented as a simple directed graph of $$$n \le 100$$$ vertices, numbered from $$$1$$$ to $$$n$$$, and $$$m \le 1000$$$ edges. The explorer is initially at vertex $$$1$$$. The amount of gas in each vertex can be represented as an array $$$a$$$, being $$$a_{i}$$$ the amount of gas at vertex $$$i$$$.

The gas will last at the labyrinth for exactly $$$k$$$ seconds. After that, the explorer will be free again. Each second, the explorer can either move to any vertex $$$v$$$ such that there exists an edge from $$$u$$$ to $$$v$$$ or stay at vertex $$$u$$$, being $$$u$$$ the vertex he is currently at, but only after being exposed to the gas in vertex $$$u$$$. Due to the magic of the labyrinth, each second, after the explorer is exposed to the gas at vertex $$$u$$$, the array $$$a$$$ will cyclically shift once to the left (i.e. simultaneously set for all $$$i$$$, $$$1 \leq i \lt n$$$, $$$a_{i}$$$ to $$$a_{i+1}$$$ and $$$a_{n}$$$ to $$$a_{1}$$$).

You need to determine what is the minimum amount of gas the explorer can be exposed to. Note that the explorer doesn't need to return to vertex $$$1$$$.

Input

The first line contains the number of vertices, edges and seconds respectively, $$$n(1 \leq n \leq 100)$$$, $$$m(0 \leq m \leq min(1000, n\cdot(n-1)))$$$ and $$$k(1 \leq k \leq 10^{9})$$$.

The next line contains $$$n$$$ integers, $$$a_{1},a_{2}\ldots,a_{n} (0 \leq a_{i} \leq 10^{9})$$$.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$, meaning that there's an edge from $$$u$$$ to $$$v(1 \leq u,v \leq n; u \neq v)$$$.

Output

Output a single integer, the minimum amount of gas the explorer can be exposed to.

Examples
Input
6 8 4
9 8 2 8 8 0
1 2
5 4
6 3
4 3
2 5
1 6
5 3
6 4
Output
18
Input
6 10 7
7 6 0 1 0 6
1 4
1 5
2 5
3 2
3 5
4 2
4 3
4 5
6 3
6 5
Output
8
Input
4 4 5
0 1 2 3
1 4
4 3
3 2
2 1
Output
0
Note

For the first sample, an optimal strategy would be:

  • At second $$$1$$$, the explorer is at vertex $$$1$$$ and is exposed to $$$9$$$ units of gas. The array $$$a$$$ changes to $$$[8,2,8,8,0,9]$$$ and the explorer moves to vertex $$$6$$$.
  • At second $$$2$$$, the explorer is at vertex $$$6$$$ and is exposed to $$$9$$$ units of gas. The array $$$a$$$ changes to $$$[2,8,8,0,9,8]$$$ and the explorer moves to vertex $$$4$$$.
  • At second $$$3$$$, the explorer is at vertex $$$4$$$ and is exposed to $$$0$$$ units of gas. The array $$$a$$$ changes to $$$[8,8,0,9,8,2]$$$ and the explorer moves to vertex $$$3$$$.
  • At second $$$4$$$, the explorer is at vertex $$$3$$$ and is exposed to $$$0$$$ units of gas. He can't move to any node.
The explorer is free after second $$$4$$$ having been exposed to $$$18$$$ units of gas, which is the minimum amount he could have been exposed to.

For the second sample, an optimal sequence of nodes (representing the node where he's at each second) would be $$$[1,4,3,2,5,5,5]$$$.

For the third sample, the explorer can always go to a vertex where the amount of venom is 0.

$$$-$$$

Idea: 3366, thehunterjames and Esomer

Preparation: Esomer

Ocurrences: Advanced 8