eolymp
bolt
Try our new interface for solving problems

Coins

Time limit 1 second
Memory limit 128 MiB

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 (1n10^9) and m (1m15). Second line contains m pairwise distinct numbers a[1], a[2], ..., a[m] (1a[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