该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Given an infix expression with parentheses reflecting the precedences of the operators, you are supposed to fill in the operands so that the expression gets the maximum result.

Here each operand is represented by x, and we only consider three operators: + (addition), - (subtraction), and * (multiplication). Each infix expression is given in a pair of parentheses like (exp1 op exp2), where exp1 and exp2 are both infix expressions.

Note: a single operand x is also an expression, and hence is represented by (x).

输入格式

Each input file contains one test case. The first line gives a positive integer $n$ ($\le 8$), which is the number of operands. The infix expression is given in the next line, with only the parentheses, operators and x's. It is guaranteed that no extra parentheses are given. Finally $n$ integer operands are given in the last line, separated by spaces. It is guaranteed that all the operands are in the range $[-10^3, 10^3]$, and the result of any calculation will not exceed the range $[-10^8, 10^8]$.

输出格式

For each case, print in a line the maximum result that can be obtained from the given expression.

样例

5
((((x)+(x))-((x)*(x)))*(x))
1 2 3 4 5

25

提示

The optimal solution is not unique. One solution may be ((((3)+(4))-((1)*(2)))*(5))=25.

限制

对于所有的测试用例,限制为400ms, 64MB