Problem Description

A quality arithmetic expression is defined as one that consists only of parentheses, numbers, multiplication symbols, and addition symbols.

A quality arithmetic expression is recursively defined as follows:

• It contains only one positive real number less than or equal to $Z_1$. This form is represented as:

$$(x)$$

For example, when $Z_1=5$, then $(4)$ is a quality arithmetic expression.

• If $A_1, A_2, \cdots, A_k (2 \le k \le K)$ are all quality arithmetic expressions, and the sum of these quality arithmetic expressions is less than or equal to $Z_k$, then

$$(A_1 + A_2 + \cdots + A_k)$$

$$(A_1 * A_2 * \cdots * A_k)$$

are also quality arithmetic expressions.

You are given an arithmetic expression where all numbers are replaced with question marks. Your task is to find the maximum value of this expression under the condition that it is a quality arithmetic expression.

Input Format

The first line contains a positive integer $K$.

The second line contains $K$ positive integers separated by spaces, representing $Z_1, Z_2, \cdots, Z_K$.

The third line contains a quality arithmetic expression where all numbers are replaced with ?. This expression consists only of ?, +, *, (, and ).

Output Format

This problem uses a Special Judge.

You need to output the maximum value of the expression.

Your solution is accepted if and only if the absolute difference between your output and the standard answer is $\le 10^{-3}$.

Sample Input and Output

Sample Input #1

2
10 6
((?)+(?))

Sample Output #1

6.00000

Sample Input #2

3
2 5 3
(((?)+(?))*(?))

Sample Output #2

6.00000

Sample Input #3

3
2 10 6
((?)*(?)*(?))

Sample Output #3

8.0000000

Notes

Sample 1 Explanation

The expression $((3)+(3))$ meets the conditions, thus it is a quality arithmetic expression. It is easy to prove that $6$ is the maximum value of this expression.

Sample 2 Explanation

The expression $(((1)+(2))*(2))$ can achieve the maximum value.

Sample 3 Explanation

The expression $((2)*(2)*(2))$ can achieve the maximum value.

Data Size and Constraints

For $100\%$ of the data, it is guaranteed that $2 \le K \le 50$, $1 \le Z_i \le 50$, and the length of the expression $\le 10^6$.

Notes

This problem is translated from COCI2016-2017 CONTEST #3 T4 Kvalitetni.

见题面 Input 部分

见题面 Output 部分