플래티넘 VThere are \(n\) souvenirs positioned around a circular street of length \(L\); souvenir \(i\) is at integer position \(p_i\) (measured clockwise from \(0\)). You start and finish at position \(0\) and may carry at most \(k\) souvenirs at once. Moving along the street costs distance equal to the arc travelled (either direction; a full loop costs \(L\)).
Output the minimum total distance to deliver every souvenir and return to \(0\).
Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.
Interaction / I/O protocol
Input. Line 1: \(n\), \(L\), \(k\). Line 2: \(n\) integers \(p_1 \dots p_n\) (\(0 \le p_i < L\)).
Output. Print one integer: the minimum total travel distance.
Example. n=4, L=10, k=2, positions 1 2 8 9: carry \(\{1,2\}\) clockwise (cost \(4\)) and \(\{8,9\}\) counter-clockwise (cost \(4\)) for a total of 8.
- \(1 \le n \le 5000\)
- \(1 \le k \le n\)
- \(1 \le L \le 10^{6}\), \(\; 0 \le p_i < L\)
Line 1: \(n\), \(L\), \(k\). Line 2: \(n\) integers \(p_1 \dots p_n\) (\(0 \le p_i < L\)).
Print one integer: the minimum total travel distance.