Problem C
Maximal Parentheticals

The Association for Curtailing Parentheses in Computations disbanded after last year’s schism regarding exponentiation. You are trying to archive and zombie-proof their documents, and have come across a series of arithmetic expressions. To make the expressions more impressive for the archive, you’ve decided to write valid parentheses into the expression to maximize what each expression evaluates to. Can you design a program to automate this task?

You may not write any operators other than parentheses, but you can write as many parentheses as you want, provided that they follow the usual rules, i.e. every opening parenthesis must have a matching closing parenthesis, and everything in between the opening and closing parenthesis must form a valid arithmetic expression.

Following mathematical conventions, two adjacent expressions without an operator in between represent an implicit multiplication, i.e. $xy = x \cdot y$. A $+$ or a $-$ at the beginning of an expression represents unary plus and minus, and the combinations $()$, $+)$, and $-)$ cannot appear in the parenthesized expression.

Input

Input consists of two lines. The first line contains a single integer $2 \leq N \leq 15$. The second line contains an arithmetic expression consisting of $N$ integers each from $0$ to $9$ inclusive and interleaved with $N-1$ operators chosen from addition + and subtraction -, with a space separating each integer and operator.

Output

Output the largest possible integer (meaning closest to $+\infty $) obtainable by writing valid parentheses into the input expression.

Explanation of samples

In sample input 1, we can write parentheses to obtain the expression $(1+2)(+3) = (1+2) \cdot 3 = 9$. In sample input 2, one possible way to obtain the maximal answer $8$ results from writing parentheses as $2(-(0+2))(-2) = 2 \cdot -2 \cdot -2 = 8$.

3
1 + 2 + 3

9

4
2 - 0 + 2 - 2

8

7
8 + 6 + 7 - 5 + 3 + 0 + 9

8937