已知一个长为 n 的数列 { a_n } 与两个数 x 和 d，求一个最小的非负整数 k，使得下列条件满足：

存在 1 \leq l \leq r \leq n，使得 r-l+1 \leq d 且 \lvert \sum_{i=l}^r (a_i+ \lfloor \sqrt{1007} k \rfloor \frac{a_i}{\lvert a_i \rvert}) \rvert \geq x。

第一行三个正整数 n,x,d (1 \leq d \leq n \leq 2 \times 10^5,1 \leq x \leq 10^{14})。

第二行含有 n 个整数，表示数列 { a_i } (1 \leq |a_i| \leq 10^9)。

输出一行一个非负整数 k。

当 k=16 时，对于 l=2,r=3，有 \lvert \sum_{i=l}^r (a_i+ \lfloor \sqrt{1007} k \rfloor \frac{a_i}{\lvert a_i \rvert}) \rvert = 1016 \geq 1007。可以证明，不存在小于 15 的 k 使得条件满足。