Numbers Game

The goal of the numbers game is to use the basic arithmetic operations (+, -, *, /) together with several given integers (from 4 to 7 of them) to get as close as possible to a given target integer. Each operation may be used any number of times, but each given integer may be used at most once (you do not have to use all of them). For example, the closest value to a target of 20 using the integers ${2, 3, 5}$ can be obtained by the expression (2+5) * 3 = 21.

Here "/" denotes integer division whose quotient is truncated toward zero (for example, 5/4 is 1 and 8/9 is 0). Write a program that computes the answer for each game.

The input consists of several games. Each game is described on two lines. The first line contains two integers $T$ and $N$, separated by a single space, denoting the target integer and the number of given integers, with $-700000 \le T \le 700000$ and $4 \le N \le 7$. The second line contains $N$ integers separated by single spaces; every integer lies between $-1000000$ and $1000000$ inclusive.

Two zeros on a line by themselves, separated by a single space (0 0), terminate the input.

For each game, print on its own line the reachable integer (as described above) that is closest to the target. If two reachable values are equally close to the target (one below it and one above it), print the smaller one.