一个优质算术表达式由括号、数字以及乘法和加法运算组成。

一个优质算术表达式按以下方式递归定义：

• 仅由一个小于或等于 $Z_1$ 的正实数组成的表达式是优质的。 这种表达式的形式如下： $$(x)$$ 例如，如果 $Z_1 = 5$，那么 $(4)$ 是一个优质表达式。
• 如果 $A_1, A_2, \dots, A_k$ 是优质表达式，满足 $2 \le k \le K$ 且这些表达式的和最多为 $Z_k$，那么以下表达式也是优质的： $$(A_1+A_2+...+A_k)$$ $$(A_1*A_2*...*A_k)$$

给你一个优质表达式，其中数字被问号（?）代替。 确定该表达式可能具有的最大值。

输入格式

第一行包含整数 $K$ ($2 \le K \le 50$)。

第二行包含整数 $Z_1, \dots, Z_K$，用空格分隔 ($1 \le Z_1, \dots, Z_K \le 50$)。

第三行包含一个符合上述格式的优质算术表达式。 算术表达式由 '?', '*', '+', '(', ')' 组成，其长度最多为 $1\,000\,000$ 个字符。

输出格式

输出该表达式的最大可能值。

如果你的答案与官方答案的绝对或相对误差小于 $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

说明

第一个样例的解释

表达式 ((3)+(3)) 满足条件，因此它是一个优质表达式，且很容易验证 $6$ 是最大值。

第二个样例的解释

例如，对于表达式 (((1)+(2))*(2))，可以达到最大值。

第三个样例的解释

例如，对于表达式 ((2)*(2)*(2))，可以达到最大值。