Problem E: Subset Sum

Maia would like to buy exactly 3.141592 litres of milk. But guess what? Her local grocery store does not stock a bag that size! So Maia decides to buy multiple bags. Even so, it might not be possible to buy a total of exactly 3.141592 litres. In that case, she is willing to buy a little bit more if necessary, but she wants to minimize the extra amount. In addition, Maia wants the bags to all be of distinct sizes, because it would be too boring to buy two bags of the same size. Maia painstakingly figures out which bags of milk to buy. But the next day, she wants 2.718281 litres of milk, and she has to figure it all out again. Clearly she needs to write a program to help her.

Input Specification

The first line of input contains two integers 0 <= n <= 1000000000 and 0 < m <= 20, the number of microlitres of milk that Maia wants, and the number of sizes of milk that the store sells. The following m lines each contain an integer 0 <= a <= 1000000000, the size of a bag of milk that the store sells (in microlitres).

Sample Input

5859870 3
3141592
2718281
1000000

Output Specification

Output a single integer, the minimum total number of microlitres of milk that Maia needs to buy in order to have at least n microlitres. If it is not possible to buy at least n microlitres, output the word IMPOSSIBLE.

Output for Sample Input

5859873

Ondřej Lhoták
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.