Knowing that UTS is moving to 30 Humbert Street, you notice the lack of restaurants in the surrounding area. In order to maximize the happiness of the students, you plan to build new ones along Humbert Street. The blocks on the street can be modelled as a 1-indexed array. Initially, there are restaurants, on blocks .
You want any consecutive segment of blocks to have at least restaurants. Additionally, no two restaurants can occupy the same block. Since you’re secretly stealing funds from the school to execute this plan, you want to minimize the total number of extra restaurants to build.
The first line contains the four integers , , , and : the length of the road, the segment length to be checked, the number of desired restaurants in each segment, and the number of restaurants that already exist, respectively.
The line contains distinct integers , the positions of the pre-existing restaurants.
Print the minimum number of restaurants that must be built in order to satisfy the conditions.
Subtask 1 [20%]
Subtask 2 [80%]
Sample Input 1
10 4 2 3 1 7 4
Sample Output 1
Explanation for Sample Output 1
One possible solution is to build restaurants on blocks 5 and 8.
Sample Input 2
5 1 1 1 4
Sample Output 2
Explanation for Sample Output 2
4 restaurants must be built, on blocks 1, 2, 3, and 5.