Один из способов придумывания задач — наблюдать за процессами в реальной жизни. Можно выбрать какую-то реально существующую ситуацию из жизни, формализовать ее и так получить новую задачу.
Представим жизненную ситуацию: стоит много людей, все ждут лифта. Каждый человек хочет попасть на какой-то конкретный этаж. Мы можем формализовать это следующим образом. Пусть n людей стоит на первом этаже, и i-й человек хочет попасть на fi-й этаж. К сожалению, в здании только один лифт, способный вместить k человек (иными словами, одновременно лифт могут использовать не более k человек). Изначально лифт расположен на первом этаже. Лифту требуется |a - b| секунд для того, чтобы доехать от a-го до b-го этажа (время, необходимое пассажирам лифта на вход и выход, не учитывается).
Какое минимальное количество секунд необходимо для того, чтобы развезти всех людей по необходимым этажам и затем вернуть лифт на первый этаж?
Выходные данные
Выведите единственное целое число — минимальное время, необходимое для достижения поставленной цели.
Примечание
В первом примере оптимальное решение выглядит так:
- Заходят люди номер 1 и 2.
- Лифт едет на второй этаж.
- Оба человека выходят из лифта.
- Лифт возвращается на первый этаж.
- Затем лифт забирает человека номер 3.
- Лифт едет на второй этаж.
- Лифт забирает человека номер 2.
- Лифт едет на третий этаж.
- Второй человек выходит.
- Лифт едет на четвертый этаж и там выходит третий человек.
- Лифт возвращается на первый этаж.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 3 4
|
8
|
|
2
|
4 2
50 100 50 100
|
296
|
|
3
|
10 3
2 2 2 2 2 2 2 2 2 2
|
8
|