Problem
In the Enchanted Land, coins of denominations A
1, A
2,..., A
M are used. The magic man came to the store and found that he had exactly two coins of each denomination. He needs to pay the amount N. Write a program to determine if he can pay without change.
Input
At the input of the program first comes the number N (1 <= N <= 10
9), then the number M (1 <= M <= 15) and then M pairwise distinct numbers A
1 , A
2,..., A
M (1 <= A
i <= 10
9 ).
Imprint
First print K - the number of coins that the Magic Man will have to give if he can pay the specified amount without change. Then print K numbers that define the values of the coins. If there are several solutions, print the variant in which the Magic Man gives the smallest possible number of coins. If there are several such options, print any of them.
If you cannot do without change, then print a single number 0. If the Magic Man does not have enough money to pay the specified amount, print a single number -1 (minus one).
| Input |
Output |
100 6
11 20 30 40 11 99
| 3
40 30 30
|