기타리스트

기타리스트 강토는 공연에서 N개의 곡을 정해진 순서대로 연주한다. 이번 공연에서는 각 곡을 시작하기 직전에만 볼륨을 조절하려고 한다.

공연 전에 길이 N의 배열 V를 정해 두었다. V[i]는 i번째 곡을 시작하기 전에 현재 볼륨에서 정확히 V[i]만큼 올리거나 내려야 한다는 뜻이다. 현재 볼륨이 P라면 i번째 곡은 P + V[i] 또는 P - V[i] 중 하나의 볼륨으로만 연주할 수 있다.

볼륨은 항상 0 이상 M 이하이어야 한다. 이 범위를 벗어나는 값으로는 조절할 수 없다.

곡의 개수 N, 시작 볼륨 S, 최대 볼륨 M, 그리고 배열 V가 주어질 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하시오. 모든 곡은 배열에 적힌 순서대로 연주해야 한다.

첫째 줄에 N, S, M이 주어진다. (1 <= N <= 50, 1 <= M <= 1,000, 0 <= S <= M)

둘째 줄에 각 곡을 시작하기 전에 조절해야 하는 볼륨 차이 V[1], V[2], ..., V[N]이 주어진다. 각 값은 1 이상 M 이하이다.

마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 출력한다. 마지막 곡까지 도달할 수 없다면 -1을 출력한다.

추가 힌트가 없습니다.