Coins#1012
In the Magic Country, coins have denominations a_1, a_2, \ldots, a_m. A magic man comes to a store and finds that he has exactly two coins of each denomination. He needs to pay an amount of . Write a program to determine whether he can pay the exact amount without change.
The first line contains two integers (1 \le n \le 10^9) and (1 \le m \le 15). The second line contains pairwise distinct integers a_1, a_2, \ldots, a_m (1 \le a_i \le 10^7).
Print the minimum number of coins that the magic man has to give if he can pay the exact amount without change. If it is not possible to pay the exact amount, print 0. If he does not have enough money to pay the amount, print -1.
Example 1
Example 2
Example 3