시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB57181528.302%

문제

Adrian owns a stock that he previously purchased, and wants to sell that stock. Currently, at day $0$, the price of the stock is $P_0$. As a robot, Morgan can predict the future. Morgan tells Adrian that the price changes will repeat every $N$ days.

Formally, suppose that the price change from day $i$ to day $i + 1$ for $0 ≤ i ≤ N - 1$ is $D_i$. The price change from day $i$ to $i + 1$ for $i ≥ N$ is $D_i = D_{i \bmod N}$. The price of the stock at day $i$ for $i > 0$ is $P_i = P_{i-1} + D_{i-1}$. It is possible for a price to be negative.

Moreover, Morgan also knows that the price is on a downward trend. That is, the sum of all $D_i$ is negative.

The following table is the stock price of each day if $N = 6$, $P_0 = 20$, and $D_{0..5} = [4, -6, -1, 4, -9, -2]$.

Day $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$ $14$ $15$ $16$ $17$ $\dots$
Price $20$ $24$ $18$ $17$ $21$ $12$ $10$ $14$ $8$ $7$ $11$ $2$ $0$ $4$ $-2$ $-3$ $1$ $-8$ $\dots$

Adrian can only sell the stock when the price is at least $X$, the price when he purchased the stock, to avoid any losses. As a thrill seeker, Adrian also would like to sell his stock at the lowest price possible while still being at least $X$.

Help Adrian to determine the lowest price of the stock that is not lower than $X$, or tell him if it is impossible. Note that Adrian can sell his stock at day $0$, if $P_0 ≥ X$.

입력

Input begins with three integers $N$ $P_0$ $X$ ($1 ≤ N ≤ 100\, 000$; $1 ≤ P_0, X ≤ 10^9$) representing the number of days in a cycle, the price at day $0$, and the price when Adrian purchased the stock, respectively. The next line contains $N$ integers $D_i$ ($-10^9 ≤ D_i ≤ 10^9$) representing the price changes that repeat every $N$ days. It is guaranteed that the sum of all $D_i$ is negative.

출력

If a price not lower than $X$ exists, output an integer in a single line representing the lowest price of the stock that is not lower than $X$. Otherwise, output -1 in a single line.

예제 입력 1

6 20 5
4 -6 -1 4 -9 -2

예제 출력 1

7

The table in the description represents this example. The lowest price of the stock that is not lower than $5$ is $P_9 = 7$.

예제 입력 2

6 20 1
4 -6 -1 4 -9 -2

예제 출력 2

1

The lowest price of the stock that is not lower than $1$ is $P_{16} = 1$.

예제 입력 3

1 3 4
-1

예제 출력 3

-1

The current price, $P_0$, is $3$ and for any subsequent day, the price will never go up. Thus, it is impossible for the price to reach at least $X = 4$.