В Волшебной стране используются монетки достоинством a[1]
, a[2]
, ..., A[m]
. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму n. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
В первой строке записаны числа n (1 ≤ n ≤ 10^9
) и m (1 ≤ m ≤ 16). Во второй строке записано m попарно различных чисел a[1]
, a[2]
, ..., a[m]
(1 ≤ a[i]
≤ 10^7
).
Выведите наименьшее количество монет k, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1.