It's a hot summer day, and Farmer John is letting Betsy go to the
water park where she intends to ride every single slide. The water
park has N (1 <= N <= 10,000) platforms (numbered 1..N) from which
to enter the M (1 <= M <= 10,000) water slides. Each water slide
starts at the top of some platform and ends at the bottom of some
platform (possibly the same one). Some platforms might have more
than one slide; some might not have any.
The park is very thin, so the platforms lie along a straight line, each platform at a position Xi (0 <= Xi <= 100,000) meters from one end of the park. One walks from one platform to the next via a sidewalk parallel to the line of platforms.
The platforms of the water park are weakly connected; that is, the park cannot be divided into two sets of platforms with no slides running between the two sets. Both the entrance and exit to the park are at platform 1, so Betsy will start and end there.
In order to spend more time on the slides, Betsy wants to walk as little as possible. Find the minimum distance Betsy must travel along the ground in order to try every slide in the park exactly once without repeating.
The input file contains multiple test cases, for each test case:
* Line 1: Two integers, N and M.
* Lines 2..N+1: Line i+1 contains one integer, Xi, the position of platform i.
* Lines N+2..M+N+1: Line i+N+1 contains two integers, Si and Di, respectively the start and end platforms of a slide.
Process till EOF.
For each test case, output:
* Line 1: One integer, the minimum number of meters Betsy must walk.
5 7 5 3 1 7 10 1 2 1 2 2 3 3 1 4 5 1 5 4 1
USACO 2006 March