Adding Parentheses 2

There is an expression of length $N$. The expression consists of integers between $0$ and $9$ inclusive and the operators +, -, and ×. Because multiplication has higher precedence than addition and subtraction, multiplication must be evaluated first. When evaluating an expression, it must be evaluated from left to right. For example, the result of $3+8×7-9×2$ is $41$.

If parentheses are added to the expression, the subexpression inside the parentheses must be evaluated first. However, each pair of parentheses must contain exactly one operator. For example, if parentheses are added to $3+8×7-9×2$ as $(3+8)×7-(9×2)$, the result is $59$. Nested parentheses are not allowed. That is, $3+((8×7)-9)×2$ and $3+((8×7)-(9×2))$ are not valid expressions because they contain parentheses inside parentheses.

Given an expression, write a program to find the maximum possible result of an expression that can be made by adding parentheses appropriately. There is no limit on the number of parentheses added, and none have to be added.

The first line gives the length of the expression, $N(1 ≤ N ≤ 19)$. The second line gives the expression. Every integer in the expression is between $0$ and $9$ inclusive. The string starts with an integer, and operators and integers alternate. Each operator is one of +, -, *. Here * denotes the × operation, which is multiplication. Because only valid expressions are given, $N$ is odd.

On the first line, print the maximum possible result of an expression obtained by adding parentheses appropriately. The answer is less than $2^{31}$ and greater than $-2^{31}$.