Олимпиадный тренинг

Задача . C. Большое смешивание

Задача

Темы: графы кратчайшие пути поиск в глубину и подобное *2300

Саша и Коля снова решили напиться колы. На этот раз у них есть k видов колы, i-й вид колы характеризуется концентрацией газа $\text{[math]}$ . Сегодня на празднике в честь Сергея Ванкуверского они решили приготовить бокал колы с концентрацией газа ровно $\text{[math]}$ . Чтобы напиток также был вкусным, они хотят, чтобы в бокале было целое число литров колы каждого вида (колы некоторых видов может и вовсе не быть в бокале). Кроме того, они хотят минимизировать общий объем колы в бокале.

Концентрацией газа в коле называется отношение объема газа к общему объему напитка. При смешивании объем газа в напитке равен суммарному объему газа в смешиваемых компонентах; объем напитка также равен сумме объемов напитка в смешиваемых компонентах.

Помогите Саше и Коле. Найдите минимальное натуральное количество литров колы, необходимое для получения бокала с концентрацией газа ровно $\text{[math]}$ . Считайте, что каждого вида колы у друзей бесконечное количество.

Входные данные

В первой строке входных данных содержится два целых числа n и k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 10⁶) — требуемая концентрация газа и количество видов колы соответственно.

Во второй строке находятся k целых чисел a₁, a₂, ..., a_k (0 ≤ a_i ≤ 1000) — концентрация газа в каждом из видов колы. Для некоторых видов колы концентрация газа может совпадать.

Выходные данные

Выведите минимальное натуральное количество литров колы, необходимое для получения бокала с концентрацией газа ровно $\text{[math]}$ , или -1, если это сделать невозможно.

Примечание

В первом примере мы можем получить концентрацию $\text{[math]}$ , используя по одному литру видов с концентрациями $\text{[math]}$ и $\text{[math]}$ : $\text{[math]}$ .

Во втором примере мы можем получить концентрацию $\text{[math]}$ , используя два литра вида $\text{[math]}$ , и один литр вида $\text{[math]}$ : $\text{[math]}$ .

Примеры

№	Входные данные	Выходные данные
1	400 4 100 300 450 500	2
2	50 2 100 25	3

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет