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?


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
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in