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

콘서트 timer 1s memory 256MB

콘서트 1s 256MB