Nescafé Tower Elevator Puzzle

An ancient tower called Nescafé Tower has N floors with an elevator that stops at every floor. The elevator is controlled by a giant handle with M control slots. Each control slot i is labeled with an integer \( C_i \) where \( C_1 < C_2 < \dots < C_M \) and there is exactly one slot with \( C_i=0 \) (the initial position of the handle).

The effect of setting the handle to a specific slot is as follows:

• If \( C_i>0 \): the elevator ascends \( C_i \) floors.
• If \( C_i<0 \): the elevator descends \( -C_i \) floors.

However, the elevator is only allowed to travel between floor 1 and floor \( N \) (inclusive). That is, if moving by \( C_i \) floors would result in a floor number outside \( [1, N] \), the move is forbidden.

The time costs are given by:

• The elevator takes \( 2 \) seconds to move one floor (i.e. if it moves \( k \) floors, it takes \( 2|k| \) seconds).
• Moving the handle from one control slot to an adjacent slot takes \( 1 \) second for each step. (For example, moving from slot i to slot j costs \( |j-i| \) seconds.)

Initially, the team is at floor 1, and the handle is at the slot with \( C_i=0 \). They want to reach floor \( N \) as quickly as possible. Determine the minimum total time needed to go from floor 1 to floor \( N \). If it is impossible to reach floor \( N \), output -1.

inputFormat

The first line contains two integers \( N \) and \( M \) (the number of floors and the number of control slots).

The second line contains \( M \) space-separated integers \( C_1, C_2, \dots, C_M \) in strictly increasing order. It is guaranteed that one of these integers is 0.

outputFormat

Output a single integer representing the minimum total time (in seconds) required to reach floor \( N \) from floor 1. If it is impossible, output -1.

sample

5 3
-1 0 2

9