Subset Sum

Time limit1sMemory limit128 MB

Summary

Given up to 20 bag sizes and a target n, pick each bag at most once to reach at least n with the smallest possible total.

Level: Easy3 of 10
Topics: Brute force, Bit manipulation, Array
Solved: No attempts yet

Problem

Maia wants to buy exactly $n$ microlitres of milk. Her grocery store does not sell a single bag of that size, so she buys several bags and adds them together. It may be impossible to reach exactly $n$ microlitres, so she is willing to buy a little more if needed, but she wants the extra amount to be as small as possible.

The store offers $m$ bag sizes. Maia refuses to buy two bags of the same size, so she may take each offered bag at most once. Choose some of the offered bags so that Maia buys at least $n$ microlitres of milk while making the total amount she buys as small as possible.

Input

The first line contains two integers $n$ and $m$ ( $0 \le n \le 1000000000$ , $0 < m \le 20$ ): the number of microlitres of milk Maia wants, and the number of bag sizes the store sells.

Each of the next $m$ lines contains one integer $a$ ( $0 \le a \le 1000000000$ ): the size, in microlitres, of one bag the store sells.

Output

Print a single integer: the minimum total number of microlitres Maia must buy so that she has at least $n$ microlitres, using each offered bag at most once. If she cannot reach at least $n$ microlitres, print IMPOSSIBLE instead.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
15 3
10
5
3
```
Expected output
```
15
```
Example 3
Input
```
100 2
10
20
```
Expected output
```
IMPOSSIBLE
```