21/11/2024 20:22:13

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2771. Коллекция

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Русалочка раскладывает свою коллекцию разноцветных жемчужин по коробкам.
Каждая коробка вмещает не более `K` жемчужин. Жемчужины могут быть одного из `M` цветов.
Количество жемчужин `i`-го цвета равно `A_i`.
Русалочка хочет, чтобы ни в одной коробке не было жемчужин с одинаковым цветом.

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

Первая строка ввода содержит два целых числа -- вместимость коробок `K` (`2 <= K <= 10^6`) и количество цветов жемчужин `M` (`1 <= M <= 10^5`).
Вторая строка ввода содержит `M` целых чисел `A_i` (`1 <= A_i <= 1000`) -- количество жемчужин `i`-го цвета.

Вывести одно целое число - минимальное количество коробок.

```sample Пример ввода
3 4
4 3 4 3
```

```sample Пример вывода
5
```

*Пояснение:* Можно разложить коллекцию следующим образом: в 1-й коробке жемчужины с номерами цветов (1,2,3), во 2-й -- (1,2,3), в 3-й -- (1,2,4), в 4-й -- (1,3,4),
в 5-й -- (3,4).