English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Coins

Maximum working time on one test: 1 second

In the Magic 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 that determines whether he will be able to pay without change.

Input data

The program input first receives 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).

Output data

First, output K - the number of coins that will have to be given to the Magic Man if he can pay the specified amount without change. Next, output K numbers specifying the coin values. If there are several solutions, output a variant in which the Magic Person will give the smallest possible number of coins. If there are several such options, output any of them.

If you can't do without the change, then output one number 0. If the Magic Man does not have enough money to pay the specified amount, print one number -1 (minus one).

Examples
Input data
100 6
11 20 30 40 11 99
Output data
3
40 30 30

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)