Execution Time

You developed a program that runs $N$ tasks in parallel. The $N$ tasks all have different execution times, and the tasks are ordered.

When a task finishes, it signals the next tasks. A task that receives a signal can run only after it has received signals from all of its preceding tasks.

As in the figure above, there are tasks $A$, $B$, $C$, $D$, $E$ and their order is fixed. We first run task $A$ and continue through task $E$. There is always exactly one task that must start first, like task $A$, and exactly one task that runs last, like task $E$.

Suppose the execution times of tasks $A$ through $E$ are 1 second, 2 seconds, 3 seconds, 2 seconds, 1 second, in that order. The five tasks run as follows.

• Time 0: first, task $A$ runs.
• Time 1: after running for 1 second, task $A$ signals tasks $B$, $C$, $D$ that it has finished.
• Time 1: tasks $B$, $C$, $D$ receive the signals, satisfy their run condition, and start at the same time.
• Time 3: tasks $B$ and $D$ have execution time 2 seconds, so 2 seconds later they signal the next task, task $E$.
• Time 3: task $E$ receives the signals but has not received a signal from task $C$ among its preceding tasks, so it waits.
• Time 4: task $C$ has execution time 3 seconds, so 3 seconds after task $C$ starts it signals task $E$.
• Time 4: task $E$ has received all signals, so it runs. Task $E$ has execution time 1 second.
• Time 5: task $E$ finishes, and the execution of all tasks ends.

Therefore, task $E$ finishes 5 seconds later.

However, it was confirmed that in this program, forcibly changing the execution times of exactly $K$ of the remaining $N-2$ tasks, excluding the task that must start first and the task that runs last, to 0 seconds causes no problem in the program.

Find the minimum time needed for all tasks to complete when the execution times of exactly $K$ tasks are forcibly changed to 0 seconds.

The number of tasks $N$, the number of task-order relations $M$, and the number of tasks whose execution time may be forcibly changed to 0 seconds, $K$, are given, separated by spaces. A task-order relation tells which task runs after a task finishes.

The second line gives the execution times of the $N$ tasks, separated by spaces.

From the third line to line $M + 2$, task-order information is given. Each piece of information consists of two integers $S$, $E$ separated by a space, meaning that task $E$ runs after task $S$ finishes.

The starting task number is always 1, and running this task guarantees that all tasks run.

Given tasks $A$, $B$, $C$, the task order is guaranteed not to contain a cycle such as $A \rightarrow B \rightarrow C \rightarrow A$.

Print the minimum time needed for all tasks to complete when the execution times of exactly $K$ tasks are changed to 0 seconds.

• $2 \le N \le 100$
• $N - 1 \le M \le 500$
• $0 \le K \le min(N - 2, 3)$
• $1 \le S, E \le N$
• $1 \le$ execution time $\le 1,000,000$, execution time is an integer