콘서트 > 문제은행



실전대비 Level8

1760 : 콘서트

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 5 회   



용재는 교내의 밴드 '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 번째 곡을 연주 할 때의 볼륨의 최대를 구하는 프로그램을 작성하라.




입력은 여러 개의 테스트 케이스로 구성된다.
입력의 첫 행에는 테스트 케이스의 수 T 가 주어진다. (1 ≤ T ≤ 100)
테스트 케이스의 첫 번째 줄에는 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



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.