This winter at Martingrove, you have decided to help out a fundraiser that is selling chocolates. In the fundraiser, ~N~ students, numbered from ~1~ to ~N~, have ordered chocolates, where the ~i^\text{th}~ student has ordered ~C_i~ chocolates for themselves. Additionally, when a student orders chocolates for themselves, they can also choose to order chocolates for some friends. Because of this, the fundraiser got ~M~ additional orders of chocolates, where in every additional order ~i~, student ~u_i~ buys student ~v_i~ some chocolates.

However, as a part of a grand marketing scheme, if student ~u_i~ wants to buy student ~v_i~ chocolates, student ~u_i~ must order student ~v_i~ the same amount of chocolates that student ~u_i~ received, including the ones that student ~u_i~ bought for themselves. Note that a student cannot give themselves another order of chocolates, or give another student multiple orders of chocolates.

Because you have been tasked with delivering the chocolates, and you do not like hard work, you wish for there to be as few sales of chocolate as possible. You can coerce ~K~ people to not buy themselves chocolates, i.e., you can set ~K~ of the ~C_i~ to ~0~. However, they will still buy chocolates for their friends. What is the minimum amount of chocolates you will have to deliver?

Constraints

~1 \leq N \leq 2 \times 10^5~

~0 \leq M \leq 2 \times 10^5~

~0 \leq K \leq N~

~1 \leq C_i \leq 10^6~

~1 \leq u_i, v_i \leq N, u_i \neq v_i~

The pair ~(u_i, v_i)~ is unique.

Before setting ~K~ of the ~C_i~ to ~0~, the total number of chocolates needed to be delivered will be less than ~10^{18}~.

There does not exist a cycle of students ~a_1, a_2, \dots, a_L~ such that student ~a_1~ sent chocolates to student ~a_2~, student ~a_2~ sent chocolates to student ~a_3~, ~\dots~, student ~a_L~ sent chocolates to student ~a_1~.

Subtask 1 [20%]

~M = N - 1~

Each student can send chocolates to at most ~1~ other student and can also receive chocolates from at most ~1~ other student.

Subtask 2 [30%]

~K = 0~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains the integers ~N~, ~M~, and ~K~, separated by a space.

The second line contains ~N~ space separated integers, where the ~i^\text{th}~ integer represents the number of chocolates ~C_i~ the ~i^\text{th}~ person will buy for themselves.

The ~i^\text{th}~ line of the next ~M~ lines will contain the integers ~u_i~ and ~v_i~ separated by a space, where student ~u_i~ will give chocolates to student ~v_i~.

Output Specification

Output a single integer, the minimum number of chocolates which you will have to deliver after coercing ~K~ students into not buying chocolates for themselves.

Sample Input 1

4 4 1
1 5 1 1
1 2
2 3
3 4
2 4

Sample Output 1

8

Explanation for Sample 1

Student ~1~ buys themselves ~1~ chocolate, receiving ~1~ chocolate in total.

Student ~2~ buys themselves ~5~ chocolates and receives ~1~ chocolate from student ~1~, receiving ~6~ chocolates in total.

Student ~3~ buys themselves ~1~ chocolate, and receives ~6~ chocolates from student ~2~, receiving ~7~ chocolates in total.

Student ~4~ buys themselves ~1~ chocolate, receives ~6~ chocolates from student ~2~ and also receives ~7~ chocolates from student ~3~, receiving ~14~ chocolates in total.

Before preventing ~K~ of the students from buying themselves chocolates, the total amount of chocolates needed to be delivered is ~1 + 6 + 7 + 14 = 28~.

The optimal solution is to make student ~2~ not buy themselves chocolates, which results in ~8~ chocolates needing to be delivered.

Sample Input 2

6 8 3
3 4 2 5 10 1
1 3
1 2
1 4
2 4
4 5
3 5
5 6
2 5

Sample Output 2

22