Коробки з сувенірами#7766

Коробки з сувенірами

1 секунда

128 мегабайтів

Дуже легка

На церемонії відкриття IOI 2015 відбувається остання дія. Кожна команда повинна отримати сувенір від країни-організатора. Але волонтери настільки захоплені церемонією, що забули про сувеніри. Єдиний, хто пам'ятає про них, — це Аман. Він ентузіаст і хоче, щоб усі команди отримали сувеніри якомога швидше.

Зал, де проходить церемонія, має круглу форму і поділений на $l$ однакових секторів, пронумерованих від $0$ до $l - 1$ l - 1. Сектори $i$ та $i + 1$ i + 1 є сусідніми для всіх $i$ від $0$ до $l - 2$ l - 2, а сектор $l - 1$ l - 1 сусідній з сектором $0$ . У залі знаходяться $n$ команд, кожна з яких сидить в одному з секторів. Деякі сектори можуть бути порожніми.

Є $n$ однакових сувенірів. Спочатку Аман і всі сувеніри знаходяться в секторі $0$ . Аман повинен роздати по одному сувеніру кожній команді і повернутися в сектор $0$ після того, як віддасть останній сувенір. В секторі $0$ також можуть бути команди.

Аман може нести не більше $k$ сувенірів одночасно. Він бере сувеніри в секторі $0$ миттєво. Кожен сувенір потрібно доставити до команди. Коли Аман досягає сектора з командами, які ще не отримали сувеніри, він може роздати сувеніри миттєво. Єдиний час, який витрачається, — це час на пересування між секторами. Аман може рухатися по колу в обох напрямках. Перехід до сусіднього сектора (в будь-якому напрямку) займає одну секунду, незалежно від кількості сувенірів, які він несе.

Ваше завдання — визначити мінімальну кількість секунд, необхідну Аману для доставки всіх сувенірів і повернення в сектор $0$ .

Вхідні дані

Перша строка містить три числа: кількість команд $n$ , максимальна кількість сувенірів, яку може нести Аман $k$ , і кількість секторів $l$ ( $1 \leq n \leq 1 0^{7}$ 1 \leq n \leq 10^7, $1 \leq k \leq n$ 1 \leq k \leq n, $1 \leq l \leq 1 0^{9}$ 1 \leq l \leq 10^9). Друга строка містить масив positions довжини $n$ . Елементи масиву positions[0], ..., positions[n - 1] задають номери секторів, в яких знаходяться команди. Елементи масиву positions впорядковані в неубувному порядку.

Вихідні дані

Виведіть мінімальну кількість секунд, необхідну Аману для виконання завдання.

Приклади

У цьому прикладі є три команди ( $n = 3$ n = 3) і $8$ секторів ( $l = 8$ l = 8), а Аман може нести два сувеніри ( $k = 2$ k = 2). Команди знаходяться в секторах $1$ , $2$ і $5$ .

Одне з оптимальних рішень показано на рисунку. За перший прохід Аман бере два сувеніри, передає один команді в секторі $2$ , другий — команді в секторі $5$ , і повертається в сектор $0$ . Це займає $8$ секунд. За другий прохід Аман доставляє останній сувенір команді в секторі $1$ і повертається в сектор $0$ . Це займає ще $2$ секунди. Загальний час доставки — $10$ секунд.

Приклад 1