콘서트

문제 정보

문제

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

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

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

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

출처: TopCoder

입력

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 T가 주어진다. (1<=T<=200)
테스트 케이스의 첫번째 줄에는 N(1<=N<=50)과 VS(0<=VS<=VM)와 VM(0<=VM<=1,000)가 주어진다.
그리고 두번째 줄에는 V1, V2, ..., VN(1<=Vi<=VM)이 차례대로 입력된다.

출력

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

예제 입력

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

노트

2개의 댓글이 있습니다.