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