| Codeforces Round 407 (Div. 1) |
|---|
| Закончено |
Саша и Коля снова решили напиться колы. На этот раз у них есть k видов колы, i-й вид колы характеризуется концентрацией газа 
. Сегодня на празднике в честь Сергея Ванкуверского они решили приготовить бокал колы с концентрацией газа ровно 
. Чтобы напиток также был вкусным, они хотят, чтобы в бокале было целое число литров колы каждого вида (колы некоторых видов может и вовсе не быть в бокале). Кроме того, они хотят минимизировать общий объем колы в бокале.
Концентрацией газа в коле называется отношение объема газа к общему объему напитка. При смешивании объем газа в напитке равен суммарному объему газа в смешиваемых компонентах; объем напитка также равен сумме объемов напитка в смешиваемых компонентах.
Помогите Саше и Коле. Найдите минимальное натуральное количество литров колы, необходимое для получения бокала с концентрацией газа ровно . Считайте, что каждого вида колы у друзей бесконечное количество.
В первой строке входных данных содержится два целых числа n и k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 106) — требуемая концентрация газа и количество видов колы соответственно.
Во второй строке находятся k целых чисел a1, a2, ..., ak (0 ≤ ai ≤ 1000) — концентрация газа в каждом из видов колы. Для некоторых видов колы концентрация газа может совпадать.
Выведите минимальное натуральное количество литров колы, необходимое для получения бокала с концентрацией газа ровно , или -1, если это сделать невозможно.
400 4
100 300 450 500
2
50 2
100 25
3
В первом примере мы можем получить концентрацию 
, используя по одному литру видов с концентрациями 
и 
: 
.
Во втором примере мы можем получить концентрацию 
, используя два литра вида 
, и один литр вида 
: 
.
