Problem Description

It is the Year 2150, and Rar has just completed his massive construction operation of a super humongous sky-scraper! Yay! With one super high-speed lift car and S floors, the building is indeed one of the most revolutionary ones of all time!

However, he quickly realises a problem. To build the building, he has dispatched his set of N peanut minions to construct the building. Now that the building is completed, there are so many peanuts that are still left stranded in the building, and there is only one lift to bring all of them down! Oh no!

The ground floor in which Rar and the lift is currently at now is defined as floor 0. The top floor will be defined as floor S. The lift car travels at 1 floor per second (as in it travels from floor 0 to floor 1 and viceversa in 1 sec), and can only hold up to H peanut minions at a time. The time that it takes to stop and pick up a peanut minion is negligible. Given a list of which floors each of the peanut minions are on, calculate the minimum possible time required for Rar to completely evacuate all his minions.

For a clearer illustration, take for example two peanut minions at floors 10 and 7, with a lift that has a capacity of 2. In this case, the lift can go to floor 7, pick up the first peanut minion, head to floor 10, pick up another peanut minion, and head back down to floor 0 to drop them off. This would take a total of 7+3+10=20 seconds.

Your program will be required to implement the following functions:

  1. long long int minTime(int N, int S, int H, int F[]), where F[] is the array containing the floor at which each peanut minion is at.


Your function will be given a description of the parameters as described above.


Your function should return the minimum time that would be needed to evacuate all the peanut minions to floor 0.


Subtask 1 (14%): 1 <= N, S, H <= 100
Subtask 2 (29%): 1 <= N, S, H <= 1 000
Subtask 3 (57%): 1 <= N, S, H <= 1 000 000

Sample Input 1

2 15 2
10 7

Sample Output 1


Sample Input 2

5 20 2
1 2 3 4 5

Sample Output 2