Stock Market

Adrian owns a stock he bought earlier and wants to sell it. On day 0, the price is $P_0$. Morgan, a robot, can predict the future. Morgan tells Adrian that the price changes repeat every $N$ days.

Formally, let $D_i$ be the price change from day $i$ to day $i + 1$ for $0 \le i \le N - 1$. For $i \ge N$, $D_i = D_{i \bmod N}$. For $i > 0$, the price on day $i$ is $P_i = P_{i-1} + D_{i-1}$. A price can be negative.

Morgan also knows the price is on a downward trend. The sum of all $D_i$ is negative.

Adrian can sell the stock only when the price is at least $X$, the price he paid for it, so that he takes no loss. He wants to sell at the lowest price that is still at least $X$. If $P_0 \ge X$, he can sell on day 0.

The first line has three integers $N$, $P_0$, and $X$ ($1 \le N \le 100\,000$; $1 \le P_0, X \le 10^9$). The next line has $N$ integers $D_i$ ($-10^9 \le D_i \le 10^9$) that repeat every $N$ days. The sum of all $D_i$ is guaranteed to be negative.

If a price at least $X$ exists, print the lowest such price on one line. Otherwise, print -1 on one line.