ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Зима — 2020» > задача:


D. Макс и коллекция сувениров

Тренировочный турнир сезона «Зима — 2020»

Старт: 09.янв.2020 в 14:00:00
Финиш: 31.янв.2020 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и кольцевая линия
• B. Макс и солдатики
• C. Макс и продажа кристаллов
• D. Макс и коллекция сувениров
• E. Макс и делегация новичков
• F. Макс и лотерея
• G. Макс и трекер шагов
• H. Макс и купюры
• I. Макс и чтение
• J. Макс и новогодние подарки
• K. Макс и оплата чека
• L. Макс и новые папки

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и коллекция сувениров
Макс и коллекция сувениров
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В продуктовом магазине рядом с домом Макса началась акция: за покупки посетителям дарят сувениры по мотивам известного мультфильма. Неожиданно, но Макс — рьяный фанат этого мультфильма, поэтому он решил во что бы то ни стало собрать всю коллекцию сувениров.

Макс выяснил у кассира правила акции. Всего в магазине есть $$$N$$$ сувениров $$$M$$$ разных видов; количество сувениров $$$i$$$-го вида — $$$A_i$$$. Каждому покупателю кассир дарит один случайный сувенир.

Макс решил, что потратит все свои сбережения, но пройдёт через кассу столько раз, сколько потребуется, чтобы собрать все виды сувениров. Помогите ему определить минимальное количество покупок, которого будет достаточно, чтобы гарантированно собрать всю коллекцию.

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

Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 10^6, 1 \le M \le 1000$$$) — соответственно общее количество сувениров в магазине и количество видов сувениров.

Вторая строка содержит $$$M$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le 1000$$$) — количество имеющихся в магазине сувениров каждого вида. Сумма всех $$$A_i$$$ равняется $$$N$$$.

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

Выведите одно целое число — минимальное количество проходов через кассу, после которых Макс гарантированно соберёт все виды сувениров.

Примеры

Входные данные
4 3
1 1 2
Выходные данные
4
Входные данные
19 5
3 4 4 3 5
Выходные данные
17

Для отправки решений необходимо выполнить вход.

www.contester.ru