Problem Description

After turning on the power of the elevator, the explorers enter the vertical tunnel where the elevator runs. In front of them is a track leading straight to the top of the tower, an elevator parked at the bottom of the track, and a huge lever inside the elevator that controls its movement up and down.

The $Nescafé$ Tower has a total of $N$ floors, and the elevator has a stop on every floor.

The lever has $M$ control slots. Next to the $i$-th slot there is a number $C_i$, satisfying $C_1 < C_2 < C_3 < \dots < C_M$.

If $C_i > 0$, it means that when the lever is moved to this slot, the elevator will go up $C_i$ floors. If $C_i < 0$, it means that when the lever is moved to this slot, the elevator will go down $-C_i$ floors. Also, there is guaranteed to be some $C_i = 0$, and the lever initially stays at this slot.

Note that the elevator can only move within floors $1 \sim N$. Therefore, it is not allowed to move the lever to a slot that would make the elevator go below floor $1$ or above floor $N$.

For each floor the elevator moves, it takes $2$ seconds. Moving the lever from one control slot to an adjacent slot takes $1$ second.

The explorers are currently on floor $1$ and want to reach floor $N$ as quickly as possible. They want to know the minimum time needed to get from floor $1$ to floor $N$.

Input Format

The first line contains two positive integers $N, M$.

The second line contains $M$ integers $C_1, C_2, \dots, C_M$.

Output Format

Output one integer, the answer: the minimum time required.

If it is impossible to reach, output $-1$.

6 3
-1 0 2

19

Hint

Constraints: It is guaranteed that $1 \le N \le 1000$, $2 \le M \le 20$, $-N < C_1 < C_2 < ...< C_M < N$.

Translated by ChatGPT 5