Unsweet Cookie

Time limit2sMemory limit512 MB

Summary

Choose up to K starting points for length-D intervals over a timeline to cover the maximum number of given points.

Level: Medium6 of 10
Topics: Greedy, Binary search, Dynamic programming
Solved: No attempts yet

Problem

Simo will eat food N times during the next T minutes. The time when each food is eaten is given as a_i.

If she drinks one cup of Gymnema sylvestre tea at time x, its effect lasts for D minutes. Therefore, the effect applies to every food eaten at a time satisfying x ≤ a_i < x + D.

Simo may drink at most K cups. Even if the effects of multiple cups overlap, the same food-eating event is counted only once. Choose when she drinks the tea to maximize the number of food-eating events covered by the effect.

Input

The first line contains four positive integers T, N, D, and K. (1 ≤ T ≤ 10^9, 1 ≤ N ≤ 10^6, 1 ≤ D ≤ 10^9, 1 ≤ K ≤ 10)

The second line contains N positive integers a_1, a_2, ..., a_N, where a_i is the time when the corresponding food is eaten. (1 ≤ a_i ≤ T)

Output

Print the maximum number of food-eating events that can be covered by choosing the tea-drinking times optimally.

Examples5

Example 1
Input
```
20 7 5 2
9 15 7 12 14 9 3
```
Expected output
```
6
```
Example 2
Input
```
9 9 1 2
2 5 6 7 2 8 9 8 9
```
Expected output
```
4
```
Example 3
Input
```
10 5 1 3
1 2 3 4 5
```
Expected output
```
3
```
Example 4
Input
```
10 10 15 1
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
10
```
Example 5
Input
```
789514 3 4 10
430 29 12470
```
Expected output
```
3
```