SUM

問題文

要素数 $N$ の数列 $A$ が与えられます。
この数列から $1$ 個以上 $N$ 個以下の要素を選び、その選んだ要素で新しい数列 $A'$ を作ります。( $A'$ の要素の順番は任意です。)
数列 $A'$ の要素の総和として考えられる値のうち、最大値を求めてください。

ただし、数列の要素は $1$ 個以上選ばなければならず、選び方の総数は $2^N - 1$ となります。

制約

• $1 \leq N \leq 15$
• $-100 \leq A_i \leq 100 \ (1 \leq i \leq N)$
• $N, \ A_i \ (1 \leq i \leq N)$ は整数

入力

N
A_1 A_2 A_3 ... A_N

• $1$ 行目に数列の要素数 $N$ が与えられます。
• $2$ 行目に数列 $A$ が与えられます。

出力

数列 $A'$ の要素の総和として考えられる値のうち、最大値を求めてください。

入力例 1

3
1 2 3

出力例 1

6

数列 $A$ の要素の全てを選んだとき、 $A'$ は例えば、$[1,2,3]$ になり、総和は、 $1 + 2 + 3 = 6$ より $6$ です。
要素の総和が $6$ より大きくなるような $A'$ の作り方は存在しないため、$6$ を出力します。

入力例 2

1
-1

出力例 2

-1