Задача
В Волшебной стране используются монетки достоинством A
1, A
2,..., A
M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Входные данные
На вход программы сначала поступает число N (1 <= N <= 10
9), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A
1, A
2,..., A
M (1 <= A
i <= 10
9).
Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
| Ввод |
Вывод |
100 6
11 20 30 40 11 99 |
3
40 30 30 |