У Чарівній країні використовуються монетки номіналом 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^7
).
Виведіть найменшу кількість монет k, яку прийдеться віддати Чарівному чоловічку, якщо він зможе заплатити вказану суму без здачі. Якщо без здачі не обійтись, то виведіть одне число 0. Якщо ж у Чарівного чоловічка не вистачить грошей, щоб заплатити вказану суму, виведіть одне число -1.