TLE '17 Contest 5 P2 - Delivery Service II

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Delivering weapons on the Great Fax.

Fax McClad, Croneria's most punctual bounty hunter, has been hastily hired by the Cronerian government to ship weapons.

There are N planets arranged in a straight line in the Lylot system, numbered from 1 to N. The i^{th} planet is located x_i spacemiles from the origin of the system. It is guaranteed that no two planets have the same location.

There are D deliveries that Fax needs to make. The j^{th} delivery consists of Fax transporting weapons from planet p_{j_1} to planet p_{j_2}, p_{j_1} \ne p_{j_2}. Fax's ship can carry an unlimited amount of weapons. This means that Fax can handle more than one delivery at once.

However, turning around costs a lot of fuel (since Fax must accelerate his ship in the opposite direction), so Fax will turn around at most once.

Fax can start anywhere along the line of planets and can start travelling in any direction. Can you tell Fax the minimum number of spacemiles that he will need to travel?

Input Specification

The first line of input will contain two space-separated integers N (2 \le N \le 10^5) and D (1 \le D \le 10^5).

N lines of input follow. The i^{th} line will contain a single integer, x_i (|x_i| \le 10^8).

D lines of input follow. The j^{th} line will contain two space-separated integers, p_{j_1} and p_{j_2}.

For 20\% of the points, N,D \le 10

For an additional 20\% of the points, |x_i| \le 100.

For an additional 20\% of the points, N,D \le 10^3.

Output Specification

Output a single integer, the minimum number of spacemiles that Fax needs to travel to complete all deliveries. If it is impossible, output -1.

Sample Input

3 3
1 3
2 3
3 2

Sample Output


Explanation for Sample Output

Fax can start at planet 2, pick up weapons on planet 1, drop the first two deliveries at planet 3 and then turn around to complete the last delivery.


There are no comments at the moment.