Коробки с сувенирами
Идет последнее действие церемонии открытия IOI 2015. Во время последнего действия каждая команда должна получить коробку с сувениром от страны организатора олимпиады. Но все волонтеры настолько увлечены церемонией, что совсем забыли про сувениры. Единственным человеком, который не забыл про сувениры, оказался Аман. Он большой энтузиаст и хочет, чтобы все команды IOI получили сувениры, при этом он хочет раздать все сувениры за наименьшее время.
Зал, где проводится церемония открытия, является круглым и разделен на l одинаковых секторов. Все секторы пронумерованы последовательно от 0 до l - 1. Таким образом, для всех i (0 ≤ i ≤ l - 2) сектор с номером i является соседним c сектором i + 1, а сектор с номером l - 1 соседний с сектором 0. В зале находятся n команд. Каждая команда сидит в одном из секторов. Каждый сектор может вместить любое количество команд. Некоторые секторы могут быть пустыми.
Имеется n одинаковых сувениров. Изначально Аман и все сувениры находятся в секторе с номером 0. Аман должен выдать один сувенир каждой команде и после того, как он отдаст последний сувенир, вернуться в сектор 0. Заметим, что в секторе 0 также могут находиться команды.
В любой момент времени Аман может нести не более k сувениров. Он должен взять сувениры в секторе 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 упорядочены в неубывающем порядке.
Выходные данные
Вывести наименьшее количество секунд, которое необходимо Аману для выполнения задачи.