Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Лифт в бизнес-центре

Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнесцентр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого
из N этажей. Определите, какое минимальное время потребуется, чтобы перевезти на парковку всех сотрудников бизнес-центра.
 
Первая строка входных данных содержит наибольшее возможное число людей в лифте K, 1 ≤ K ≤ 109
Вторая строка содержит число этажей в бизнес-центре N, 1 ≤ N ≤ 105
 
Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1, 2, … , N-м этаже соответственно, эти числа не превосходят 109  каждое. В здании находится хотя бы один человек. 

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

Ввод Вывод Примечание
2
3
3
0
1
8 Лифт перевозит 2 человек, в здании 3 этажа. Лифт поднимается на первый этаж за 1 с, забирает 2 человек и за 1 с спускается на парковку, затем лифт поднимается на первый этаж, забирает 1 человека, вместе с ним поднимается на третий этаж, забирает 1 человека и спускается на парковку. Подъём на третий этаж занимает 3 с, спуск – ещё 3 с.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

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


Нет

Примечание учителя: