Problems
Coins
Coins
In the Magic Country the coins have the next values a[1]
, a[2]
, ..., a[m]
. 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 data
First row contains numbers n (1 ≤ n ≤ 10^9
) and m (1 ≤ m ≤ 15). Second line contains m pairwise distinct numbers a[1]
, a[2]
, ..., a[m]
(1 ≤ a[i]
≤ 10^7
).
Output data
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.
Examples
Input example #1
5 2 1 2
Output example #1
3
Input example #2
7 2 1 2
Output example #2
-1
Input example #3
5 2 3 4
Output example #3
0