Remote Control

Interview

Time limit2sMemory limit256 MB

Summary

Given a target channel and a set of broken digit buttons, compute the minimum button presses to reach the channel from 100 using digits, plus and minus.

Level: Medium4 of 10
Topics: Brute force, String, Implementation, Math
Solved: No attempts yet

Problem

Subin is watching TV. Some numeric buttons on the remote control are broken, so it may be impossible to enter every desired channel number directly.

The remote has numeric buttons from 0 through 9 and the + and - buttons. Pressing + moves to the channel that is 1 higher than the current channel, and pressing - moves to the channel that is 1 lower. If - is pressed on channel 0, the channel stays at 0. There is no upper limit on channel numbers.

The current channel is 100. Given the list of broken numeric buttons, find the minimum number of button presses needed to move to the target channel N.

Input

The first line contains the target channel N. (0 <= N <= 500,000)

The second line contains the number M of broken numeric buttons. (0 <= M <= 10)

If M is at least 1, the third line contains the M broken numeric buttons separated by spaces. The same button is not listed more than once.

Output

Print one line containing the minimum number of button presses needed to move to channel N.

Hint

Using only + or - from channel 100 is also a candidate answer. Also compare it with entering some channel using only working numeric buttons first, then correcting to the target with + or -.

Examples7

Example 1
Input
```
5457
3
6 7 8
```
Expected output
```
6
```
Example 2
Input
```
100
5
0 1 2 3 4
```
Expected output
```
0
```
Example 3
Input
```
500000
8
0 2 3 4 6 7 8 9
```
Expected output
```
11117
```
Example 4
Input
```
100
3
1 0 5
```
Expected output
```
0
```
Example 5
Input
```
14124
0
```
Expected output
```
5
```
Example 6
Input
```
1
9
1 2 3 4 5 6 7 8 9
```
Expected output
```
2
```
Example 7
Input
```
80000
2
8 9
```
Expected output
```
2228
```