Петя хочет построить длинный забор. Он уже нашел хорошее место, чтобы построить его, и все, что остается — это собрать необходимые материалы.
В местном магазине продают доски всего n разных длин, однако досок каждого типа можно купить сколько угодно. Чтобы избежать отходов, Петя хочет, чтобы общая длина этих досок была в точности равна длине забора l.
По заданной длине забора и типам досок, найдите минимальное число досок, которое Пете нужно приобрести для того, чтобы получить забор нужной длины.
Будьте готовы, забор будет очень длинный!
Первая строка входного файла содержит количество тестов t, Далее следуют описания тестов.
Каждый тест состоит из двух строк. Первая строка содержит два целых числа l и n — общую длину забора и количество различных длин досок, которые можно купить. Вторая строка n целых чисел b1, b2, ..., bn — возможные длины досок.
Ограничения: 1 ≤ t ≤ 50, 1010 ≤ l ≤ 1018.
В задаче 1: 1 ≤ bi ≤ 100.
В задаче 2: 1 ≤ bi ≤ 100000.
Для каждого теста выведите минимальное число досок, необходимых для того, чтобы построить забор. Если построить забор невозможно, выведите - 1.
2
10000000001 3
23 51 100
10000000001 3
100 52 22
100000004
-1
В первом примере нужно взять 2 доски длиной 23, 5 досок длиной 51 и 99999997 досок длиной 100. Конечно, можно было бы использовать только 100000001 доску длиной 100, но тогда длина будет больше l.
Во втором примере можно получить только четные длины.