Hide

Problem G
Gondolas

The most adventurous part of skiing is the journey onto the mountain-top, between trees and through clouds, and past all sorts of enchanting views.

Naturally, the skiers at the foot of the lift can hardly wait to take their turns (although they are a little disappointed that the climb will eventually terminate). They all know exactly which times they plan to catch a lift on the tireless rotary machine.

Unfortunately, there are only so many gondolas available at the start of the day to attach to the track loop. The track loop takes $2 \cdot T$ minutes to cycle around ($T$ on the way up and then $T$ on the way back down). Given that you can arrange the gondolas on the track however you see fit, what is the minimum summed waiting time of all skiers that you can achieve?

Input

  • One line containing three integers:

    • $N$ ($1 \le N \le 400$), the number of skiers.

    • $T$ ($1 \le T \le 720$), the time to travel from the bottom of the hill to the top in minutes.

    • $G$ ($1 \le G \le 400$), the number of available gondola cabs.

  • A further $N$ lines in no particular order, each containing one integer $X$ ($0 \le X \le 10^6$) which gives the time when a skier arrives at the foot of the mountain.

Output

  • One line containing one integer: the minimum possible sum of all waiting times, where the waiting time for one skier is the time difference between their arrival and departure on the next available gondola (which may be shared with any number of other skiers).

Sample Input 1 Sample Output 1
4 10 2
0
15
30
45
10
Sample Input 2 Sample Output 2
4 10 3
0
15
30
45
5
Sample Input 3 Sample Output 3
5 16 3
16
7
5
8
1
4

Please log in to submit a solution to this problem

Log in