This winter at Martingrove, you have decided to help out a fundraiser that is selling chocolates. In the fundraiser, students, numbered from to , have ordered chocolates, where the student has ordered 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 additional orders of chocolates, where in every additional order , student buys student some chocolates.
However, as a part of a grand marketing scheme, if student wants to buy student chocolates, student must order student the same amount of chocolates that student received, including the ones that student 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 people to not buy themselves chocolates, i.e., you can set of the to . However, they will still buy chocolates for their friends. What is the minimum amount of chocolates you will have to deliver?
Constraints
The pair is unique.
Before setting of the to , the total number of chocolates needed to be delivered will be less than .
There does not exist a cycle of students such that student sent chocolates to student , student sent chocolates to student , , student sent chocolates to student .
Subtask 1 [20%]
Each student can send chocolates to at most other student and can also receive chocolates from at most other student.
Subtask 2 [30%]
Subtask 3 [50%]
No additional constraints.
Input Specification
The first line contains the integers , , and , separated by a space.
The second line contains space separated integers, where the integer represents the number of chocolates the person will buy for themselves.
The line of the next lines will contain the integers and separated by a space, where student will give chocolates to student .
Output Specification
Output a single integer, the minimum number of chocolates which you will have to deliver after coercing 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 buys themselves chocolate, receiving chocolate in total.
Student buys themselves chocolates and receives chocolate from student , receiving chocolates in total.
Student buys themselves chocolate, and receives chocolates from student , receiving chocolates in total.
Student buys themselves chocolate, receives chocolates from student and also receives chocolates from student , receiving chocolates in total.
Before preventing of the students from buying themselves chocolates, the total amount of chocolates needed to be delivered is .
The optimal solution is to make student not buy themselves chocolates, which results in 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
Comments