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.
Input Format
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 next lines each contain a single integer. The
line contains the integer
, the positions of the
pre-existing restaurant. No two pre-existing restaurants will have the same position.
Output Format
Print the minimum number of restaurants that must be built in order to satisfy the conditions.
Subtasks
Subtask 1 [20%]
Subtask 2 [80%]
Sample Input 1
10 4 2 3
1
7
4
Sample Output 1
2
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
4
Explanation for Sample Output 2
4 restaurants must be built, on blocks 1, 2, 3, and 5.
Comments
This problem previous had invalid data and an incorrect input format. The problem statement has been modified to reflect the actual input format, and the invalid cases have been removed. All out of contest submissions have been rejudged.