P6884 [COCI 2016/2017 #3] Kvalitetni

定义一个算术表达式是有质量的，当且仅当这个算术表达式只由括号，数字，乘法符号和加法符号组成。 一个有质量的算术表达式由下列方式递归定义： - 仅包含一个正实数**小于等于** $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}$。

#### 样例 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T4 Kvalitetni_**。