{"timeLimit":2000,"input":"Первая строка входного файла содержит количество тестов $t$, Далее следуют описания тестов.\r\n\r\nКаждый тест состоит из двух строк. Первая строка содержит два целых числа $l$ и $n$ --- общую длину забора и количество различных длин досок, которые можно купить. Вторая строка $n$ целых чисел $b_1, b_2, \\ldots, b_n$ --- возможные длины досок.\r\n\r\nОграничения: $1\\le t\\le 50$, $10^{10}\\le l\\le 10^{18}$.\r\n\r\nВ задаче 1: $1\\le b_i\\le 100$.\r\n\r\nВ задаче 2: $1\\le b_i\\le 100000$.\r\n","sampleTests":[{"input":"2\r\n10000000001 3\r\n23 51 100\r\n10000000001 3\r\n100 52 22\r\n","output":"100000004\r\n-1\r\n"}],"legend":"Петя хочет построить длинный забор. Он уже нашел хорошее место, чтобы построить его, и все, что остается --- это собрать необходимые материалы.\r\n\r\nВ местном магазине продают доски всего $n$ разных длин, однако досок каждого типа можно купить сколько угодно. Чтобы избежать отходов, Петя хочет, чтобы общая длина этих досок была в точности равна длине забора $l$.\r\n\r\nПо заданной длине забора и типам досок, найдите минимальное число досок, которое Пете нужно приобрести для того, чтобы получить забор нужной длины.\r\n\r\nБудьте готовы, забор будет очень длинный!\r\n","outputFile":"stdout","name":"Очень длинный забор","authorName":"Pavel Mavrin","inputFile":"stdin","tutorial":"","language":"russian","notes":"В первом примере нужно взять 2 доски длиной 23, 5 досок длиной 51 и 99999997 досок длиной 100. Конечно, можно было бы использовать только 100000001 доску длиной 100, но тогда длина будет больше $l$.\r\n\r\nВо втором примере можно получить только четные длины.","output":"Для каждого теста выведите минимальное число досок, необходимых для того, чтобы построить забор. Если построить забор невозможно, выведите $-1$.","authorLogin":"pashka","memoryLimit":67108864}