Reordering to Maximize (f_n)

You are given an array of (n) integers (a_1,a_2,\ldots,a_n). Define (f_0=0) and for (i\ge 1) define

[ f_i = \begin{cases} f_{i-1}, & \text{if } f_{i-1}\times a_i > 0,\[1mm] f_{i-1}+a_i, & \text{if } f_{i-1}\times a_i \le 0. \end{cases} ]

You are allowed to reorder the array (a) arbitrarily. Your task is to choose an ordering so that the final value (f_n) is maximized.

It turns out that an optimal strategy works as follows:

1. If there is at least one non-positive number (i.e. (\le 0)) then choose \n (r = \max{a_i:,a_i\le 0}) (if there is a negative number, this is the negative number closest to (0); if only zeros exist then (r=0)).

2. Let (P) be the list of positive numbers. In any valid ordering the numbers that are actually added (rather than skipped) are exactly those elements placed at positions where the current sum (f) and the element have opposite signs or (f=0). In particular, when (r<0) it is possible to have one or more positive elements added as long as the partial cumulative sum remains (\le 0). Suppose we plan to have a block of positive numbers (S) to be added (in some order) and then later the remaining positive (say a candidate (x)) appears when (f) is already non–positive, so that it gets added and makes (f) positive – after that, no further positive is added. (Any later negative will be added and decrease (f); hence, it is best to postpone negatives to positions where they are skipped.)

3. Thus, if we denote by (s) the sum of all positive numbers that are added before the final addition and if (x) is the final positive added, then the final value will be

[ f_n=r+s+x. ]

The constraint is that while adding the positives in (S) the cumulative sum must remain (\le 0); that is,

[ r+s\le 0\quad \text{(and for any proper prefix of }S\text{, the partial sum is also (\le0))}. ]

Since you may choose the order arbitrarily among the positives, an optimal solution is obtained by partitioning (P) into two parts: a set (S) (possibly empty) whose sum does not exceed (-r) so that when added to (r) the result is still non–positive, and a candidate positive (x) (taken from (P\setminus S)) which, when appended, makes the final value

[ r+s+x, (>0)]

as high as possible. (If no positive number exists then the answer is simply (r). Also, if all numbers are positive then the answer is (\max(P)) because only the first element will be added.)

Your task is to compute the maximum final value (f_n) achievable by an optimal reordering.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 50\)).

The second line contains \(n\) space–separated integers \(a_1,a_2,\ldots,a_n\) (\(|a_i| \le 10^9\)).

outputFormat

Output a single integer: the maximum possible value of \(f_n\) obtainable by reordering the array.

sample

5
-1 1 3 4 -2

4