시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3211939.130%

문제

The cows just learned to add and subtract. They've written down an expression containing N terms (1 ≤ N ≤ 10) such as the following:

1 + 4 - 2 - 1 + 10 - 6

Bessie (the smart cow) realizes that this expression can evaluate to different numbers depending on how it is parenthesized. Help her determine the maximum possible number to which it can evaluate.

입력

  • Line 1: The single integer N
  • Lines 2..1+N: Each line contains an integer between -100 and 100 (inclusive) and corresponds to one term in the expression. A positive number K corresponds to + K in the expression and a negative number -K corresponds to - K in the expression.

출력

  • Line 1: The maximum value to which the expression can evaluate, if properly parenthesized.

예제 입력 1

6
1
4
-2
-1
10
-6

예제 출력 1

20

힌트

1 + 4 - (2 - (1 + 10) - 6) = 20