Michael has discovered a strange planetary system consisting of planets numbered from
to
.
The planets happen to orbit in such a way that they align in a straight line in front of the central star at all times. Each planet is located kilometers away from the central star. The distance between any two planets
and
is equal to
. Michael starts on planet
and wants to visit all
planets, but his spaceship has a limited number of kilometers it can travel before needing to be refueled. His spaceship can be refueled back to full capacity after landing on any planet.
Additionally, some planets are locked behind force fields that prevent any visitors. These force fields can be deactivated remotely on designated planets. A planet may have multiple force fields, in which case all of them need to be deactivated before visiting it. There are such force fields, the
th of which is present on planet
and can be disabled on planet
.
Michael needs to buy a fuel tank for his spaceship, but wants to minimize the size of the fuel tank in order to cut costs. A fuel tank of capacity can travel
kilometers when full. What is the smallest capacity
that will allow Michael to complete his journey?
Constraints
All are distinct.
All force fields are pairwise distinct.
Michael starts on a planet without any force fields and it is possible to disable all the force fields.
Subtask 1 [40%]
Subtask 2 [30%]
Subtask 3 [30%]
No additional constraints.
Input Specification
The first line of input contains integers ,
, and
.
The next line of input contains space-separated integers representing
. Planet
is located at distance
.
The next lines of input each contain integers
and
, representing a force field present on planet
that can only be disabled from planet
.
Output Specification
Output the smallest capacity that will allow Michael to travel to all the planets starting from planet
.
Sample Input
4 4 1
5 2 7 9
2 1
3 2
4 3
4 2
Sample Output
3
Comments