Choosing Three Numbers

Interview

Time limit2sMemory limit128 MB

Summary

Given N and a forbidden set S, find positive integers x, y, z not in S that minimize |N - xyz|.

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

Problem

You are given a positive integer N and a set S containing M positive integers.

Choose positive integers x, y, and z, each of which is not in S. Find the minimum possible value of |N - xyz|.

Input

The first line contains N (1 <= N <= 1,000) and M (0 <= M <= 50), the size of S.

The second line contains the numbers in S, separated by spaces. Each number is a positive integer at most 1,000, and no number appears more than once.

If M is 0, the second line is empty.

Output

Print the minimum possible value of |N - xyz| on the first line.

Examples3

Example 1
Input
```
4 2
2 4
```
Expected output
```
1
```
Example 2
Input
```
10 1
1
```
Expected output
```
2
```
Example 3
Input
```
10 2
1 2
```
Expected output
```
17
```