게임 쇼!

SBC(Sociedade de Bons Competidores)는 소속 경쟁자들을 위해 TV 쇼를 개최한다(이제는 온라인으로도 송출한다!). SBC는 sbec이라는 크레딧 시스템을 사용하는데, 이 크레딧으로 대회에 참가하거나 시즌이 끝날 때 상품으로 교환할 수 있다. SBC는 새로운 종류의 게임을 시작했고, 상금에서 큰 손해를 보지 않기 위해 몇 가지 시뮬레이션을 해야 한다!

이 새로운 게임에 참가하려면 경쟁자는 100 sbec을 걸어야 하고, 그 금액은 게임 내 잔고로 옮겨진다. 그리고 상자들이 일렬로 놓인다. 게임은 라운드로 진행되며 최대 라운드 수는 상자의 수와 같다. 각 라운드에서 플레이어는 다음 상자를 열지, 게임을 끝낼지 결정한다. 게임을 끝내면 현재 잔고의 sbec을 돌려받는다. 상자를 열면 그 안에 든 비밀 숫자가 잔고에 더해지고 게임은 계속된다. 비밀 숫자가 음수일 수 있으므로, 너무 욕심을 부린 플레이어는 손해를 보고 끝날 수도 있다! 게임은 플레이어가 끝내기로 하거나 마지막 상자를 열었을 때 종료된다.

SBC는 당신을 고용해 게임을 시험하게 했다. 상자의 내용이 주어질 때, 플레이어가 얻을 수 있는 최대 상금은 얼마인지 판단해야 한다.

입력의 첫째 줄에는 게임의 상자 수를 나타내는 정수 C가 주어진다. (1 ≤ C ≤ 100)

그다음 C개의 줄에는 순서대로 C개 상자의 내용이 주어진다. 각 줄에는 해당 상자의 내용을 나타내는 정수 V가 주어진다. (−1000 ≤ V ≤ 1000)

출력은 한 줄이며, 해당 상자 순서에서 얻을 수 있는 최대 상금을 나타내는 정수 하나를 출력한다.