IOI2015 Souvenir Distribution

Aman is a dedicated volunteer at the IOI2015 opening ceremony. Every team should receive a commemorative souvenir packaged in a box. Unfortunately, all the other volunteers were distracted by the spectacular opening ceremony, leaving Aman as the only one to distribute the souvenirs. The ceremony venue is a circular field divided into L equal regions, numbered from 0 to L-1 consecutively. Regions i and i+1 (for 0 ≤ i ≤ L-2) are adjacent, and region L-1 is adjacent to region 0.

There are N teams seated in these regions (each region might have any number of teams, including none). Aman starts at region 0 with all N identical souvenirs. Each team must receive exactly one souvenir. Note that some teams may be seated at region 0. After distributing the last souvenir, Aman must return to region 0.

Aman can carry at most K souvenirs at a time. He picks up souvenirs from region 0 without spending any time. Once he leaves region 0 with some souvenirs, he may either deliver one souvenir to a team (if he reaches a region where a team has not yet received one) or continue carrying them. The act of delivery (giving one souvenir) happens instantly upon arriving in a region (even if Aman is carrying more than one souvenir, he can only deliver one souvenir per visit to that region). The only time spent is on moving between adjacent regions. Aman may move clockwise or counterclockwise, but moving between any two adjacent regions takes exactly 1 second regardless of how many souvenirs he is carrying.

Your task is to calculate the minimum total time (in seconds) required for Aman to distribute souvenirs to all teams and return to region 0. To note, teams seated in region 0 can receive their souvenirs immediately from the start without any travel.

Hint: For teams not in region 0, the optimal strategy is to partition deliveries by direction. For a team seated in region x (x ≠ 0), the distance from region 0 is min(x, L-x). Group the teams by the direction that gives the smaller distance and, from each group, plan trips that deliver at most K souvenirs in one go. For each trip, Aman travels from region 0 to the farthest team in that trip and then returns to region 0, costing twice the farthest distance in that trip.

The formula for the required time is given by:

[ T = 2\sum_{\text{each trip}} d_{\max} ]

where \(d_{\max}\) is the distance (in seconds) to the farthest team delivered in that particular trip.

inputFormat

The input consists of two lines.

The first line contains three integers L, K, and N — the number of regions on the circular field, the maximum number of souvenirs Aman can carry at once, and the total number of teams, respectively.

The second line contains N integers. Each integer represents the region number (0-indexed) where a team is seated. Note that some teams might be seated in region 0.

outputFormat

Output a single integer — the minimum total time (in seconds) required for Aman to deliver a souvenir to each team and return to region 0.

sample

10 2 5
0 1 1 9 8

6