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^\text{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^\text{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^\text{th}~ line will contain a single integer, ~x_i~ ~(|x_i| \le 10^8)~.

~D~ lines of input follow. The ~j^\text{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
0
-2
4
1 3
2 3
3 2

Sample Output

12

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.