Ritisha works at Giza Gifts, the official souvenir shop for the Great Pyramids of Giza. Unfortunately, she'd much rather be studying topological sorting and bipartite matching like a dedicated competitive programmer.

Every minute, some number of tourists visit Giza Gifts and buy various overpriced souvenirs. By default, all customers leave unsatisfied.

Ritisha's boss has noticed this, and is watching her closely. If at least ~k~ customers leave unsatisfied within any consecutive ~t~ minutes, then Ritisha will get in trouble.

Luckily, Ritisha has recently learned a mindfulness technique. Each time she uses it, she remains calm for the next ~s~ minutes, and all customers during that period leave satisfied.

Ritisha would like to avoid angering her boss while using this technique as little as possible. What is the minimum number of times she needs to use the technique to avoid her boss's wrath?

Input

The first line contains four integers ~n~ (~1 \leq n \leq 10^5~), ~k~ (~1 \leq k \leq 10^9~), ~t~ and ~s~ (~1 \leq t \leq s \leq n~), where:

• ~n~ is the number of minutes Ritisha is working at Giza Gifts today.
• ~k~ is the number of customers that need to leave unsatisfied within any consecutive ~t~ minutes, for Ritisha to get in trouble.
• ~s~ is the number of consecutive minutes for which the mindfulness technique remains effective after being used.

The next line contains ~n~ integers, ~c_1\ \dots\ c_n~, where ~c_i~ is the number of customers who visit the store at minute ~i~.

Output

Output the minimum number of times Ritisha needs to use her mindfulness technique (which makes all customers satisfied for the next ~s~ minutes) so that, in every consecutive ~t~-minute window, fewer than ~k~ customers leave unsatisfied.

Example

Input 1

7 16 3 2
8 3 5 7 7 1 4

Output 1

1

Without using her technique, there are two ~3~-minute windows where ~\ge 16~ customers leave Giza Gifts unsatisfied.

By using her technique at ~t = 3~, there are now no ~3~-minute windows where ~\ge 16~ customers leave Giza Gifts unsatisfied.

Input 2

8 10 4 3
9 8 2 3 4 1 8 9

Output 2

2

One solution is to use the technique at ~t = 1~ and ~t = 7~.

Input 3

5 5 4 4
1 1 1 1 1

Output 3

0

There are no ~4~-minute windows where ~\ge 5~ customers leave unsatisfied, so Ritisha doesn't need to use her technique at all.