2031번 - 이 쿠키 달지 않아!

최근 심모 양(17)은 친구 사모 양(17)이 알바를 하는 허브차 카페에서 독특한 경험을 했습니다. 바로 다이어트 효과가 있는 김네마 실베스터라는 허브를 알게 된 건데요, 신기하게도 김네마 실베스터 차를 마시면 일시적으로 단맛을 느끼지 못하게 된다고 합니다. '김네마 다이어트'를 시작하기로 마음먹은 심모 양은 자신의 식습관을 고려해서 미래 T 분 동안 먹을 N 종류의 음식에 대해 각각의 음식을 먹을 시각을 분 단위로 표시한 길이 N의 목록을 만들었습니다. 김네마 실베스터 차 한 잔을 마시면 D 분 동안 다이어트 효과가 유지되는데, 심모 양은 총 K 잔의 김네마 실베스터 차를 적당한 타이밍에 마셔서 다이어트 효과가 유지되는 동안 음식을 먹는 횟수를 최대로 하기로 했습니다.

예를 들어 D = 5, K = 2이고 심모 양의 목록이 다음과 같다고 합시다.

9, 15, 7, 12, 14, 9, 3

이때 심모 양이 두 잔의 차를 3분, 9분에 마시면 첫 번째 잔은 3분에 먹는 음식부터 7분까지 먹는 음식까지에 (8분에 먹는 음식에는 효과가 있지 않습니다), 두 번째 잔은 9분에 먹는 음식부터 13분에 먹는 음식까지에 효과가 있습니다. 따라서 효과가 적용되는 횟수는 총 5번입니다.

9, 15, 7, 12, 14, 9, 3

한 편 두 잔의 차를 7분, 12분에 마시면 다음과 같이 효과가 적용되는 횟수가 6번이 되고, 이때가 최대입니다.

9, 15, 7, 12, 14, 9, 3

첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 10⁹, 1 ≤ N ≤ 10⁶, 1 ≤ D ≤ 10⁹, 1 ≤ K ≤ 10)

두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a₁, ..., a_N이 주어집니다. (1 ≤ a_i ≤ T)

첫 번째 줄에 심모 양이 적당한 타이밍에 김네마 실베스터 차를 마셨을 때 효과가 적용되는 횟수의 최댓값을 출력합니다.