Problem D
Cash Transport

CSN just sent you this month’s student loan. Finally, you have enough money to rent DBus, the computer science student division’s very own van! You’ve thought about going on a road trip but as the responsible student you are you’ve decided to use this possibility to earn money. And is there a better strat in the capitalist grind than robbing armored cash transports?

There are $N$ banks. Bank $i$ has a balance of $a_ i$ on day $0$. During the following $M$ days there will be a cash transport every day. A cash transport goes from bank $a$ to bank $b$ and takes all of the money in bank $a$ and gives it to bank $b$. During your time with DBus you will have time to rob $K$ cash transports (not necessarily consecutively). How much money can you rob at most?

Input

The first line of input contains three integers $N$, $M$ and $K$ ($1 \le N \le 3 \cdot 10^5$, $1 \le M \le 3 \cdot 10^5$ and $1 \le K \le M$).

The second line contains $N$ space-separated integers $a_0, a_1, \ldots , a_ N$ ($0 \le a_ i \le 10^9$), denoting the initial balance of bank $i$.

The following $M$ lines contains integers $a$ and $b$ ($0 \le a, b < N$, $a \neq b$). Each pair describes a cash transport between banks $a$ and $b$.

Output

Output a single integer: the maximum amount you can steal from the cash transports.

4 3 1
9 3 1 1
0 1
0 2
1 3

12