efficient-engineer

As an engineer and would like to improve the quality of duct tapes that your firm manufactures. An entire tape can be represented as a single ray of N cells. Each cell has its "Chipku" factor, which stands for its ability to stick to an object. We say that a tape is a acceptable quality product, iff the total sum of  "Chipku" factors of grid cells in any of its sub ray of size K is at least D.

To make a quality product, consider an augment operation in which you can choose any sub ray of size at most K and a real number (say R), and multiply "Chipku" factor of all its cells by R. For each augment operation, the sub ray and the value of R can be chosen arbitrarily. However, the size of chosen sub ray for augmentation can be at most K, as mentioned before.

Your task is to calculate the minimum number of augment operations required to be carried out in order to mold the given tape to a sellable quality product.

INPUT

The first line contains three space separated integers N, K and D, as described above. The next line contains N space separated integers, ith of which (denoted by Ai) denotes the "Chipku" factor of ith cell.

OUTPUT

Output in single line, an integer, which denotes the minimum number of augment operations needed to be carried out in order to mold the tape to a sellable quality product. In case, if it is impossible to achieve, print -1.

CONSTRAINTS

1 ≤ N,
 D ≤ 105,
1 ≤ K ≤ N,
0 ≤ Ai ≤ 1000.

SAMPLE INPUT
3 2 4
1 1 1

SAMPLE OUTPUT
1

Explanation

You can multiply the second element by 3. Now the tape becomes: 1 3 1.
Any sub ray of size 2 has now sum = 4, which satisfies the requirement. We used 1 augment operation, hence the solution is 1.

Source: hackerearth | Difficulty: EASY


Solutions: