## TLE '17 Contest 5 P2 - Delivery Service II

View as PDF

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

Author:
Problem type
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 planets arranged in a straight line in the Lylot system, numbered from to . The planet is located spacemiles from the origin of the system. It is guaranteed that no two planets have the same location.

There are deliveries that Fax needs to make. The delivery consists of Fax transporting weapons from planet to planet , . 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 and .

lines of input follow. The line will contain a single integer, .

lines of input follow. The line will contain two space-separated integers, and .

For of the points,

For an additional of the points, .

For an additional of the points, .

#### 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 , pick up weapons on planet , drop the first two deliveries at planet and then turn around to complete the last delivery.