## Singularity Cup P3 - Interplanetary Travel

View as PDF

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 512M

Author:
Problem types

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.

#### 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