COPS: Cows On Pogo Sticks

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest jumps for a pogo stick to go from 0 to L, where velocity changes by at most 1 per jump and cow pie points cannot be landed on.

Level: Medium5 of 10
Topics: BFS, Dynamic programming
Solved: No attempts yet

Problem

Bessie the Cow wants to use a pogo stick to travel along a cow path of integer length $L$ . She starts at point 0 and makes integer-length pogo jumps to land exactly on point $L$ . Her velocity $V$ starts at zero and is always nonnegative. At the start of each bounce, she can change her velocity by -1, 0, or +1. The velocity is the distance she travels along the path during that bounce. She can have any nonnegative velocity when she lands on point $L$ .

Bessie wants to avoid cow pies, small heaps of manure at some integer points along the path. The cow pies are not located at point 1 or point $L$ .

Find the smallest number of bounces needed to reach point $L$ exactly.

Input

The first line has two integers $L$ and $N$ ( $1 \le L \le 500$ is the path length, $1 \le N \le 250$ is the number of cow pies). Each of the next $N$ lines has the integer location of one cow pie.

Output

Print one integer: the minimum number of bounces for Bessie to reach point $L$ without landing on any cow pie. Print -1 if no such path exists.

Examples1

Example 1
Input
```
18 3
5
10
15
```
Expected output
```
6
```