In the Magic Country the coins have the next values a1, a2, ..., am. Magic man came into the store and discovered that he has exactly two coins of each value. He must pay the amount of n. Write a program, to determine whether he can pay without change.

Input

First row contains numbers n (1 ≤ n ≤ 109) and m (1 ≤ m ≤ 15). Second line contains m pairwise distinct numbers a1, a2, ..., am (1 ≤ ai ≤ 107).

Output

Print the smallest number of coins k, that have to give Magic man, if he could pay this amount without change. If you can pay without change, print 0. If the Magic man did not have enough money to pay the amount, print -1.