Коробки з сувенірами
На церемонії відкриття IOI 2015 відбувається остання дія. Кожна команда повинна отримати сувенір від країни-організатора. Але волонтери настільки захоплені церемонією, що забули про сувеніри. Єдиний, хто пам’ятає про них, — це Аман. Він ентузіаст і хоче, щоб усі команди отримали сувеніри якомога швидше.
Зал, де проходить церемонія, має круглу форму і поділений на l однакових секторів, пронумерованих від 0 до l - 1. Сектори i та i + 1 є сусідніми для всіх i від 0 до l - 2, а сектор l - 1 сусідній з сектором 0. У залі знаходяться n команд, кожна з яких сидить в одному з секторів. Деякі сектори можуть бути порожніми.
Є n однакових сувенірів. Спочатку Аман і всі сувеніри знаходяться в секторі 0. Аман повинен роздати по одному сувеніру кожній команді і повернутися в сектор 0 після того, як віддасть останній сувенір. В секторі 0 також можуть бути команди.
Аман може нести не більше k сувенірів одночасно. Він бере сувеніри в секторі 0 миттєво. Кожен сувенір потрібно доставити до команди. Коли Аман досягає сектора з командами, які ще не отримали сувеніри, він може роздати сувеніри миттєво. Єдиний час, який витрачається, — це час на пересування між секторами. Аман може рухатися по колу в обох напрямках. Перехід до сусіднього сектора (в будь-якому напрямку) займає одну секунду, незалежно від кількості сувенірів, які він несе.
Ваше завдання — визначити мінімальну кількість секунд, необхідну Аману для доставки всіх сувенірів і повернення в сектор 0.
Приклад
У цьому прикладі є три команди (n = 3) і 8 секторів (l = 8), а Аман може нести два сувеніри (k = 2). Команди знаходяться в секторах 1, 2 і 5.
Одне з оптимальних рішень показано на рисунку. За перший прохід Аман бере два сувеніри, передає один команді в секторі 2, другий — команді в секторі 5, і повертається в сектор 0. Це займає 8 секунд. За другий прохід Аман доставляє останній сувенір команді в секторі 1 і повертається в сектор 0. Це займає ще 2 секунди. Загальний час доставки — 10 секунд.
Вхідні дані
Перша строка містить три числа: кількість команд n, максимальна кількість сувенірів, яку може нести Аман k, і кількість секторів l (1 ≤ n ≤ 10^7, 1 ≤ k ≤ n, 1 ≤ l ≤ 10^9). Друга строка містить масив positions довжини n. Елементи масиву positions[0], ..., positions[n - 1] задають номери секторів, в яких знаходяться команди. Елементи масиву positions впорядковані в неубувному порядку.
Вихідні дані
Виведіть мінімальну кількість секунд, необхідну Аману для виконання завдання.