Mohannad is very fat. His doctor told him that if he consumes more than $k$ calories over the next $n$ days, he won't be allowed to play league of legends anymore. He also gave Mohannad a diet that allows him to reduce the amount of calories he takes every day by a factor of $r$ ($i.e.$ if he was going to consume $c$ calories, his diet allows him to consume $\lfloor\frac{c}{r} \rfloor$ calories).

Mohannad hates dieting, but he also wants to keep playing League of Legends. So he wants to diet for $d$ consecutive days, such that $d$ is as small as possible and he's still allowed to play League of Legends.

Given the number of calories that Mohannad was planning on eating the next $n$ days, help Mohannad by telling him the minimum number of consecutive days that he needs to diet on.

The first line contains three integers $n, k, r\ (1\leq n\leq 10^5, 1\leq k,r\leq 10^9)$, the number of days, the maximum total number of calories that Mohannad is allowed to consume, and the factor by which the diet reduces the calories that Mohannad consumes.

The second line contains $n$ integers $a_1,\ a_2,\ ...\ a_n\ (1\leq a_{i}\leq 10^4)$, the number of calories that Mohannad was originally planning on eating on the $i^{th}$ day.

Print a single integer $d$, the number of days that Mohannad needs to diet on, such that $d$ is as small as possible. If there's no way for Mohannad but to stop playing League of Legends then print $-1$.

In the first example Mohannad went on a diet from the $4^{th}$ day to the $10^{th}$ day adding $\lfloor\frac{49}{10} \rfloor = 4$ calories which makes the total sum of calories equal to $10$.