Монетки

У Чарівній країні використовуються монетки номіналом 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.

Приклади