Numbers Game

The objective of the numbers game is to use the basic arithmetic operations (+, -, * and /) and a number of given integers (4 to 7 integers) to get as close as possible to a given target integer. Each of the operations can be used multiple times, but each of the integers can be used at-most once. A player wins if he/she manages to calculate the closest possible value to the target integer. For example, the closest possible value to a target of 20 using the integers {2,3,5} can be achieved by the expression (2+5) * 3. Your task is to write a program to calculate the answer for each game. Note that “/” stands for integer division (examples are: 5/4 equals 1, 8/9 equals 0.)

The input consists of many games. The description for each game is given on two lines. The first line contains two integers T and N, separated by a single space, that represent the target integer and the number of given integers. -700,000 <= T <= 700,000 and 4 <= N <= 7. The second line contains N integers separated by single spaces. All integers have values between -1,000,000 and 1,000,000 inclusive. Two zeros on a line by themselves, separated by a single space, terminate the input.

For each game, the output consists of a single line that contains the closest possible integer to the target. Any answer with the smallest distance to the target is correct.

30 5
1 2 3 4 5
10000 5
11 2 3 7 5
0 0

30
2310

The 2011 South Pacific Programming Contest