문제

A quality arithmetic expression consists of brackets, number and operations of multiplication and addition. A quality arithmetic expression is defined recursively in the following way: ● An expression consisting of only one positive real number smaller than or equal to $Z_{1}$ is of good quality. Such expression is of the following form: (x) ● For example, if $Z_{1}$ = 5, then (4) is a quality expression. ● If $A_{1}$, $A_{2}$, …, $A_{k}$ are quality expressions such that 2 ≤ k ≤ K and the sum of these expressions is at most $Z_{k}$, then the following expressions are of good quality: ($A_{1}$ +$A_{2}$ +...+$A_{k}$) ($A_{1}$ *$A_{2}$ ...$A_{k}$) You are given a quality expression where the numbers are replaced by question marks. Determine the maximal possible value that the expression could have had.

입력

The first line of input contains integer K (2 ≤ K ≤ 50). The second line of input contains integers $Z_{1}$, …, $Z_{K}$, separated by space (1 ≤ $Z_{1}$, …, $Z_{K}$ ≤ 50). The third line of input contains one quality arithmetic expression in the described format. Arithmetic expression consists of: ‘?’, ‘*’, ‘+’, ‘(‘, ‘)’, and its length is 1 000 000 characters, at most.

출력

You must output the maximal possible value of the expression. A solution is considered correct if the absolute or relative deviation from the official solution is less than $10^{-3}$.

예제 입력 1

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

예제 출력 1

6.00000

예제 입력 2

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

예제 출력 2

6.00000

예제 입력 3

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

예제 출력 3

8.000000000