the-way-to-the-ring

Mr. Frodo and Samwise Gamjee are on their quest to find "The Magical ring".

But the path to "The ring" isn't easy.They are now stuck in their way because of 
N metre long river.

Fortunately,there is a shop which has infinite supply of wooden logs of
specific lengths but each piece of wooden log has same price irrespective of their length.

As Samwise isn't interested in spending a lot so he wants to know the minimum number of logs he should buy that should be enough to make them
cross the N metre long river.He isn't even sure whether they can cross the river by using logs of available length as the shopkeeper won't give them wooden logs
if any of the log is not fully used.

Can you help him?

INPUT:
1st line contains T- no. of test cases
1st line of each test case contains N-the length of river in metre.
2nd line of each test case contains M-the number of different length of log available in that shop.
Next line contains M-space distinct integers Ai each specifying the length of wooden log in metre available in that shop.
OUTPUT:
For each test case,output a single line containing the minimum number of logs needed to cross the river of
N metre length.Output "-1" if they are unable to cross the river using log of available lengths.
CONSTRAINTS
1 ≤ T ≤ 10

1 ≤ N ≤ 500

1 ≤ M ≤ 500

1 ≤ Ai ≤ 500

SAMPLE INPUT
2
4
3
3 5 6
11
3
1 3 5

SAMPLE OUTPUT
-1
3

Explanation

In 1st case N=4,Clearly as neither of the combination of wooden log,i.e.,of (3+3),5 or 6 would be able to make up a length of 4 metre so,it will be a case where 
shopkeeper won't give them extra log as some log may be left unused.So they are unable to cross the river.
In 2nd case N=11,and log of lengths 1,3 and 5 are available.Samwise and Frodo can use minimum 3 logs of length (5+5+1) to make up a length of 11 metre.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: