33085번 - Stock Market 다국어

문제

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]$.

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.

제한

힌트