Gift Boxes

The opening ceremony of an international contest is almost over. Every team was supposed to receive a gift box from the organizers during the ceremony, but the volunteers were so caught up in the show that they forgot about the gifts. Aman is the only one who remembers. He is an eager volunteer, and because he wants the contest to run perfectly, he plans to deliver every gift in the shortest possible time.

The ceremony hall is a circle split into $L$ equal sectors. The sectors are numbered $0$ through $L-1$ in order, so for every $i$ with $0 \le i \le L-2$ sector $i$ and sector $i+1$ are adjacent, and sector $0$ and sector $L-1$ are adjacent as well. There are $N$ teams at the ceremony. Each team sits in one sector. A sector may hold several teams, and it may hold none.

All gifts are identical and there are $N$ of them. At the start Aman and all $N$ gifts are in sector $0$. He has to hand one gift to every team and then return to sector $0$. Note that sector $0$ may hold teams too.

Aman carries at most $K$ gifts at any moment. He picks gifts up only in sector $0$, and picking them up takes no time. He keeps each gift until he hands it to a team. When Aman carries at least one gift and reaches a sector where a team is still waiting, he can hand a gift to that team. Handing a gift over takes no time either. Only walking takes time. Aman can move in both directions around the circle. Moving between two adjacent sectors takes exactly 1 second, clockwise or counterclockwise, and the number of gifts he carries does not change that.

Find the minimum number of seconds Aman needs to deliver every gift and get back to sector $0$.

Consider the case $N = 3$, $K = 2$, $L = 8$ with teams in sectors 1, 2 and 5.

The picture shows one optimal plan. Aman takes two gifts, gives one to the team in sector 2 and the other to the team in sector 5, then keeps walking the same way back to sector $0$. That part takes 8 seconds. He then brings the last gift to the team in sector 1 and walks back, which takes 2 more seconds. The total is 10 seconds.

The first line contains the number of teams $N$, the maximum number of gifts $K$ that Aman can carry at once, and the number of sectors $L$, separated by spaces.

The second line contains the sector numbers $p_0, p_1, \dots, p_{N-1}$ of the teams, separated by spaces. These numbers are given in nondecreasing order.

Print the minimum number of seconds Aman needs to deliver every gift and get back to sector $0$.

• $1 \le N \le 10^5$
• $1 \le K \le N$
• $1 \le L \le 10^9$
• $0 \le p_0 \le p_1 \le \dots \le p_{N-1} \le L-1$