Description

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:

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

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.

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

Output Format

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}$.

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

6.00000

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

6.00000

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

8.0000000

Hint

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 CONTEST #3 T4 Kvalitetni.

Translated by ChatGPT 5