Задача №113740. Лифт в бизнес-центре
Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнес- центр представляет собой N -этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого из N этажей. Определите, какое минимальное время потребуется, чтобы перевезти на парковку всех сотрудников бизнес-центра.
Первая строка входных данных содержит наибольшее возможное число людей в лифте K , 1 ≤ K ≤ 10 9 . Вторая строка содержит число этажей в бизнес-центре N , 1 ≤ N ≤ 10 5 . Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1 , 2 , … , N -м этаже соответственно, эти числа не превосходят 10 9 каждое. В здании находится хотя бы один человек.
Программа должна вывести ровно одно целое число – наименьшее время в секундах, за которое всех людей можно перевезти на парковку.
Решение, правильно работающее только для случаев, когда N ≤ 100 и количество людей на каждом этаже не превосходит 100 , будет оцениваться в 40 баллов.
Решение, правильно работающее только для случаев, когда N ≤ 100 , а дополнительного ограничения на число людей нет, будет оцениваться в 70 баллов.
2 3 3 0 1
8