Adding Parentheses

Time limit0.5sMemory limit512 MB

Summary

Parenthesize a single-digit expression with non-nested single-operator parentheses to maximize its left-to-right value.

Level: Hard8 of 10
Topics: Dynamic programming, Recursion, Brute force, Math
Solved: No attempts yet

Problem

There is an expression of length N. The expression consists of integers between 0 and 9 inclusive and the operators (+, -, ×). All operators have the same precedence, so the expression must be evaluated from left to right. For example, 3+8×7-9×2 evaluates to 136.

When parentheses are added to the expression, the subexpression inside a pair of parentheses must be evaluated first. 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 41. Nested parentheses are not allowed. That is, 3+((8×7)-9)×2 and 3+((8×7)-(9×2)) are both invalid because each has parentheses inside parentheses.

Given an expression, write a program that finds the maximum possible result of the expression when parentheses are added appropriately. There is no limit on the number of parentheses added, and adding none is allowed.

Input

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 multiplication, the × operation. Only valid expressions are given, so N is odd.

Output

Print the maximum result obtainable by adding parentheses appropriately. The answer is less than 231 and greater than -231.

Examples5

Example 1
Input
```
9
3+8*7-9*2
```
Expected output
```
136
```
Example 2
Input
```
5
8*3+5
```
Expected output
```
64
```
Example 3
Input
```
7
8*3+5+2
```
Expected output
```
66
```
Example 4
Input
```
19
1*2+3*4*5-6*7*8*9*0
```
Expected output
```
0
```
Example 5
Input
```
19
1*2+3*4*5-6*7*8*9*9
```
Expected output
```
426384
```