TOO EASY Cookie Run

Cookie Run is a popular game in which a cookie character runs through a map of N stages to score points.

Soo Young, the map designer for Cookie Run, was preparing a new map patch for Children's Day. After she finished building an attractive map and testing it for the last time the day before the patch, she realized the map was designed to be too easy.

The map follows these rules.

• Each stage has a difficulty level $A\_0, A\_1, A\_2, ..., A\_{N-1}$. The higher the difficulty, the harder the stage is to pass.
• If the sum of consecutive stages' difficulty levels is at least $M$, the section is called an interesting section. That is, if $A\_i + A\_{i+1} + ... + A\_j \geq M$, the section $(i, j)$ is an interesting section.
• The map must have at least $K$ interesting sections.

In other words, let $T$ be the number of pairs $(i, j)$ with $0 \le i \le j \le N-1$ and $A\_i + ... + A\_j \geq M$. Then $T \geq K$ must hold.

Soo Young requested help from participants of the KAIST RUN Spring Contest. All she can do is add difficulty $X$ to all stages at once to make the map harder. Find the smallest non-negative integer $X$ that satisfies these conditions.

The first line contains three space-separated integers $N$, $M$, and $K$.

The second line contains $N$ space-separated integers $A\_{0}, A\_{1}, \cdots, A\_{N-1}$.

Print a single non-negative integer, the smallest $X$ that satisfies the conditions.

You can assume that at least one non-negative integer $X$ exists that satisfies the given conditions.

• $1 \le N \le 100\,000$
• $1 \le M \le 10^{18}$
• $1 \le K \le \frac{N (N+1)}{2}$
• $0 \le A\_{i} \le 10^9$ $(0 \le i \le N-1)$