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?
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 a single integer: the maximum amount you can steal from the cash transports.
|Sample Input 1||Sample Output 1|
4 3 1 9 3 1 1 0 1 0 2 1 3