Numbers Game

Time limit5sMemory limit128 MB

Summary

Given 4 to 7 integers, combine each at most once with +, -, *, or truncated integer division to reach a value as close as possible to a target, printing the smaller value on ties.

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

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

Expected output

30
2310

Example 2
Input
```
24 4
1 2 3 4
0 0
```
Expected output
```
24
```
Example 3
Input
```
-100 4
-5 20 3 2
0 0
```
Expected output
```
-100
```