题目描述

定义一个算术表达式是有质量的，当且仅当这个算术表达式只由括号，数字，乘法符号和加法符号组成。

一个有质量的算术表达式由下列方式递归定义：

• 仅包含一个正实数小于等于 $Z_1$。这种表达形式如下：

$$(x)$$

例如当 $Z_1=5$，那么 $(4)$ 就是有质量的算术表达式。

• 如果 $A_1,A_2,\cdots,A_k(2\le k\le K)$ 都是有质量的算术表达式，并且这些有质量的算术表达式的和小于等于 $Z_k$，那么

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

也是有质量的算术表达式。

你会得到一条所有数字都被问号代替的算术表达式，求满足这个表达式是有质量的算术表达式的前提下，这个表达式可能的最大值。

输入格式

第一行包含一个正整数 $K$。

第二行包含 $K$ 个被空格隔开的正整数，表示 $Z_1,Z_2,\cdots,Z_K$。

第三行包含了一个所有数字被 ? 代替的算术质量表达式。这个表达式只包含 ?,+,*,(,)。

输出格式

本题采用 Special Judge。

你需要输出这个表达式的最大值。

你的解被接受当且仅当你的输出和标准答案的绝对值 $\le 10^{-3}$。

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

6.00000

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

6.00000

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

8.0000000

提示

样例 1 解释

表达式 $((3)+(3))$ 满足条件，因此它是一个算术表达式。容易证明，$6$ 是这个表达式的最大值。

样例 2 解释

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

样例 3 解释

对于表达式 $((2)*(2)*(2))$ 可以得到最大值。

数据规模与约定

对于 $100\%$ 的数据，满足 $2\le K\le 50,1\le Z_i\le 50$，表达式的长度 $\le 10^6$。

说明

题目译自 COCI2016-2017 CONTEST #3 T4 Kvalitetni。