Задача №114189. Лифт в бизнес-центре
В прошлом году на муниципальном этапе была задача про сотрудников бизнес-центра, которые вечером выходят с работы. Теперь решите задачу про сотрудников бизнес-центра, которые утром приходят на работу.
Бизнес-центр представляет собой \(N\)-этажное здание, этажи пронумерованы от 1 до \(N\) снизу вверх. На каждом этаже работает ровно один сотрудник. Все сотрудники утром приезжают на парковку, которая расположена в подвальном помещении, на один этаж ниже первого. Бизнес-центр оборудован лифтом, который вмещает неограниченное число людей, но вредный лифтёр сегодня готов отвезти всех сотрудников только на один какой-то этаж.
У каждого сотрудника есть выбор: он может пойти вверх пешком по лестнице, на подъём на один этаж при этом будет уходить \(A\) секунд. Либо он может сесть в лифт, который отвезёт всех сотрудников на какой-то выбранный ими вместе этаж. Выйдя из лифта, сотрудник может подняться до своего этажа (также тратя \(A\) секунд на подъём на один этаж), либо спуститься до нужного этажа вниз, тратя \(B\) секунд на спуск на один этаж. Лифт тратит \(C\) секунд на подъём на один этаж.
Определите минимальное время, за которое все сотрудники разойдутся по своим этажам, если они наилучшим образом выберут этаж, на который едет лифт, и свою стратегию поведения (подниматься по лестнице или ехать на лифте, а затем идти по лестнице).
Формат входных данных
Первая строка входных данных содержит число \(N\) — количество этажей в бизнес-центре. Следующие три строки содержат числа \(A\), \(B\), \(С\) — время, необходимое сотруднику на подъём на один этаж, на спуск на один этаж и время, необходимое лифту на подъём на один этаж. Все числа — целые положительные, не превосходящие \(2\times 10^9\), при этом \(A \ge B\), \(A \ge С\).
Формат выходных данных
Программа должна вывести единственное целое число — минимальное время, за которое все сотрудники могут добраться до своего этажа.
Пояснение к примеру из условия
В здании 6 этажей. Сотрудник поднимается на один этаж за 20 секунд, спускается за 10 секунд. Лифт поднимается на один этаж за 5 секунд.
Чтобы быстрее всем добраться до мест, лифт едет на 5-й этаж за 25 секунд. Сотрудник, который работает на 6-м этаже, выходит из лифта и поднимается за 20 секунд, всего его путь занимает 45 секунд. Сотрудник, работающий на 3-м этаже, едет на лифте и спускается на 2 этажа, это также занимает 45 секунд. Сотрудники с 4 и 5-го этажей также едут на лифте, их путь будет быстрее 45 секунд. На 1 и 2‑й этажи сотрудники поднимаются пешком по лестнице за 20 и 40 секунд соответственно. Итого все сотрудники добираются до своих этажей не более чем за 45 секунд.
Система оценивания
Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 40 баллов.Решение, правильно работающее только для случаев, когда все входные числа не превосходят \(10^5\), будет оцениваться в 70 баллов.
6 20 10 5
45