#1012 콘서트

98  2 s   128 MB  

Description

용재는 교내의 밴드 Algorhythm의 멤버이며 기타를 맡고 있다. 이번에 Algorhythm은 축제를 맡아 알고리즘 강의 시간에 공연을 하게 되었다. 용재는 특이한 기타 리스트인데, 같은 볼륨으로 모든 곡을 연주 하는걸 원치 않는다.

따라서 용재는 다음과 같은 방법으로 매 곡마다 볼륨을 바꾸려고 한다.

공연 준비 때 볼륨은 용재가 직접 정하고, 나머지는 전체적인 볼륨을 조절하는 당신에게 맡겼다. 준비 할 때의 볼륨은 $V_S$ 이다. 용재는 당신에게 메모에 $N$ 개의 숫자 $V = {V_1 , V_2, ..., V_N }$을 적어줬는데, $i$번째 곡이 연주되기 전에 현재 볼륨에 $V_i$ 만큼 더하거나 빼달라고 요청했다. 그리고 덧붙여서 마지막 곡이 연주될 때에는 클라이막스 부분이기 때문에 반드시 소리를 최대한 크게 조절해달라고 부탁했다. 또한 절대로 볼륨은 $0$보다 작을 경우가 발생 해서는 안되고, $V_M$ 를 넘지 말아야 한다는 것도 당부하였다.

예를 들어 $V_S=5$, $V_M=10$이고 $V={5, 3, 7}$ 일 경우 처음에 $5$를 빼서 볼륨을 $0$을 만든 다음, $3$을 더해서 볼륨을 $3$으로 만들고, 마지막에 $7$을 더하면 볼륨은 $10$이 되며, 이 경우는 가능한 모든 경우 중에 마지막의 볼륨을 최대화 한 경우이다.

용재의 부탁대로 볼륨을 조절할 때 $N$ 번째 곡을 연주 할 때의 볼륨의 최대를 구하는 프로그램을 작성하라.

Input

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 $T$ 가 주어진다. $(1 \leq T \leq 200)$

테스트 케이스의 첫번째 줄에는 $N$ $(1 \leq N \leq 50)$과 $V_S$ $(0 \leq V_S \leq V_M )$ 와 $V_M$ $(0 \leq V_M \leq 1, 000)$가 주어진다. 그리고 두번째 줄에는 $V_1 , V_2 , \dots , V_N$ $(1 \leq V_i \leq V_M)$ 이 차례대로 입력된다.

Output

각 테스트 케이스의 순서대로 곡을 연주할 때의 볼륨의 최대를 한줄에 하나씩 출력하며, 만약 도중에 볼륨이 $0$미만으로 떨어지거나 $V_M$ 를 초과 할 수 밖에 없는 경우가 발생할 경우에는 -1을 출력한다.

Sample Input

Sample Output

3
3 5 10
5 3 7
4 8 20
15 2 9 10
14 40 243
74 39 127 95 63 140 99 96 154 18 137 162 14 88
10
-1
238

Source

2009 Ajou University Programming Contest