P6884 [COCI 2016/2017 #3] Kvalitetni

An arithmetic expression is defined as “high-quality” if and only if it consists only of parentheses, numbers, the multiplication sign, and the addition sign. A high-quality arithmetic expression is defined recursively as follows: - It contains only one positive real number that is **less than or equal to** $Z_1$. The form of such an expression is: $$ (x) $$ For example, when $Z_1 = 5$, then $(4)$ is a high-quality arithmetic expression. - If $A_1, A_2, \cdots, A_k \ (2 \le k \le K)$ are all high-quality arithmetic expressions, and the sum of these high-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 high-quality arithmetic expressions. You are given an arithmetic expression in which **all numbers are replaced by question marks**. Under the condition that this expression is a high-quality arithmetic expression, find the maximum possible value of this expression.

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 high-quality arithmetic expression where all numbers are replaced by `?`. This expression contains only `?`, `+`, `*`, `(`, `)`.

**This problem uses Special Judge**. You need to output the maximum value of this expression. Your solution is accepted if and only if the absolute difference between your output and the standard answer is $\le 10^{-3}$.

#### Explanation for Sample 1 The expression $((3) + (3))$ satisfies the conditions, so it is a high-quality arithmetic expression. It is easy to prove that $6$ is the maximum value of this expression. #### Explanation for Sample 2 For the expression $(((1) + (2)) * (2))$, the maximum value can be achieved. #### Explanation for Sample 3 For the expression $((2) * (2) * (2))$, the maximum value can be achieved. ### Constraints For $100\%$ of the testdata, it holds that $2 \le K \le 50$, $1 \le Z_i \le 50$, and the expression length is $\le 10^6$. ### Notes **Translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T4 Kvalitetni_**. Translated by ChatGPT 5