Finding the Password

Interview

Time limit1sMemory limit512 MB

Summary

Find the smallest positive integer P such that for every element a of A, the difference a - (P mod a) equals K.

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

Problem

To enter Seunghyeon's company, one must type a password that changes every day according to a rule.

One day, Seunghyeon arrived at the company 1 minute before the start of work. Let's write a program that quickly finds the password for Seunghyeon, who is at risk of being late!

The rule for the password is as follows.

An integer K and an array A consisting of N integers are given.
When the password is divided by each element of array A, the difference between the divisor and its remainder is always K.
The password always exists, and it is the smallest positive integer among the numbers that satisfy the second rule.

Input

The first line gives the integers K and N, separated by a space. (1 ≤ K < min(Ai), 2 ≤ N ≤ 8)

The second line gives the elements of array A, which consists of N distinct integers, separated by spaces. (3 ≤ Ai ≤ 40)

Output

Print the password on the first line.

Examples2

Example 1
Input
```
4 3
9 8 7
```
Expected output
```
500
```
Example 2
Input
```
3 5
4 9 5 12 15
```
Expected output
```
177
```