Description

A guitarist is preparing for a performance. He does not like to use the same volume throughout the show, so he decides that before each song he will change the volume once. Before the show starts, he makes a list that records by how much he wants to change the volume before each song. Each time he changes the volume, he can either turn it up or turn it down.

The volume is described by an integer. In the input, the integer $beginLevel$ represents the guitar’s initial volume, and the integer $maxLevel$ represents the guitar’s maximum volume. The volume cannot be less than $0$ or greater than $maxLevel$. The input also gives $n$ integers $c_1,c_2,c_3,\cdots,c_n$, which means that before the $i$-th song begins, the guitarist wants to change the volume by that amount.

The guitarist wants to play the last song at the highest possible volume; your task is to find that maximum volume.

Input Format

The first line contains three integers $n$, $beginLevel$ and $maxLevel$.

The second line contains $n$ integers $c_1,c_2,c_3,\cdots,c_n$.

Output Format

Output the maximum possible volume for the last song. If the guitarist cannot avoid the volume going below $0$ or above $maxLevel$, output -1.

3 5 10
5 3 7

10

Hint

$1\le n\le 50$, $1\le c_i\le maxLevel$, $1\le maxLevel\le 1000$, $0\le beginLevel\le maxLevel$.

Translated by ChatGPT 5