IOI '15 - Almaty, Kazakhstan

Boxes with Souvenirs

The last act of the IOI 2015 opening ceremony is in progress. During the opening ceremony, each team was supposed to receive a box with a souvenir from the host. However, all volunteers are so fascinated by the ceremony that they completely forgot about the souvenirs. The only person who remembers about the souvenirs is Aman. He is an enthusiastic volunteer and he wants the IOI to be perfect, so he wants to deliver all the souvenirs in the least amount of time.

The venue of the opening ceremony is a circle divided into L identical sections. The sections around the circle are numbered consecutively from 0 to L − 1. That is, for 0 ≤ i ≤ L − 2, sections i and i + 1 are adjacent, and also sections 0 and L − 1 are adjacent. There are N teams at the venue. Each team is sitting in one of the sections. Each section may contain arbitrarily many teams. Some sections may even be empty.

There are N identical souvenirs. Initially, both Aman and all of the souvenirs are in section 0. Aman should give one souvenir to each team, and after delivering the last souvenir he must return to section 0. Note that some teams may be sitting in section 0.

At any moment, Aman can only carry at most K souvenirs. Aman must pick up souvenirs in section 0, and this takes him no time. Each souvenir must be carried until it is delivered to one of the teams. Whenever Aman carries one or more souvenirs and reaches a section with a team that has not received a souvenir yet, he may give that team one of the souvenirs he carries. This also happens instantly. The only thing that takes time is movement. Aman can move around the circular venue in both directions. Moving to an adjacent section (either clockwise or counterclockwise) takes him exactly one second, regardless of how many souvenirs he carries.

Your task is to find the smallest number of seconds Aman needs to deliver all souvenirs and then return to his initial position.

Example

In this example we have N = 3 teams, Aman's carrying capacity is K = 2, and the number of sections is L = 8. The teams are located in sections 1, 2, and 5.

One of the optimal solutions is shown in the picture above. In his first trip Aman takes two souvenirs, delivers one to the team in section 2, then the other to the team in section 5, and finally he returns to section 0. This trip takes 8 seconds. In his second trip Aman brings the remaining souvenir to the team in section 1 and then returns to section 0. He needs another 2 seconds to do this. Thus, the total time is 10 seconds.

Your task is, given N, K, L, and the positions of all teams, compute the smallest number of seconds Aman needs to deliver all the souvenirs and return to section 0.

Input Format

Line 1 of input will contain three space-separated integers N, K, and L, respectively representing the number of teams, the maximum number of souvenirs Aman can carry at the same time, and the number of sections in the venue of the opening ceremony.
Line 2 of input will contain positions, an array of length N. The space separated integers positions[0], …, positions[N − 1] give the section number of all teams. The elements of positions are in non-decreasing order.

Output Format

You should output a single integer – the smallest number of seconds in which Aman can complete his task.

Sample Input

3 2 8
1 2 5

Sample Output

10

Subtasks

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 2048M
Added: Sep 05, 2015

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)