Quality Expressions

A quality expression is built from brackets, numbers, multiplication, and addition.

Quality expressions are defined recursively.

• An expression that consists of a single positive real number at most $Z_1$ is a quality expression. Such an expression has the form $(x)$. For example, if $Z_1 = 5$, then $(4)$ is a quality expression.
• If $A_1, A_2, \ldots, A_k$ are quality expressions, $2 \le k \le K$, and the sum of their values is at most $Z_k$, then the following two expressions are quality expressions as well.

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

You are given a quality expression in which every number has been replaced by a question mark. Find the maximal value the original expression could have had.

The first line contains an integer $K$. ($2 \le K \le 50$)

The second line contains the integers $Z_1, \ldots, Z_K$, separated by spaces. ($1 \le Z_i \le 50$)

The third line contains one quality expression in the format described above. The expression consists only of the five characters ?, *, +, (, ), and its length is at most 1,000,000.

Print the maximal value of the expression on one line, rounded to exactly six decimal places.

Take $K = 2$, $Z_1 = 10$, $Z_2 = 6$, and the expression ((?)+(?)). Replacing both question marks by 3 gives ((3)+(3)), where the two subexpressions have values summing to $6$, which is at most $Z_2$, so it is a quality expression and its value is $6$. No larger value is possible.