No testdata at current.

https://www.luogu.com.cn/problem/T310722

最小的数字

题目描述

元元在黑板上先写下了 $N$ 个数字 $a_1,a_2,...,a_n$，又写下了 $N-1$ 个运算符，运算符仅包含+或*。

要求每次取出不一定相邻的两个数，并依次使用给出的运算符对这两个数进行运算，运算后擦去使用的运算数，并将运算后结果当做一个新数写在黑板上，继续执行前面的操作。直到黑板上只有一个数。

请问黑板上最后可能出现的最小值是多少？

输入格式

共有三行。

第一行一个整数 $N$；

第二行 $N$ 个整数 ，以空格分割；

第三行 $N-1$ 个符号，仅包含+或*以空格分割。

输出格式

输出一行，一个整数，表示黑板上可能出现的最小值。

样例 #1

样例输入 #1

4
1 1 1 1
+ + *

样例输出 #1

3

样例 #2

样例输入 #2

4
2 2 2 2
* * +

样例输出 #2

8

样例 #3

样例输入 #3

5
23 62 78 11 29
+ * * +

样例输出 #3

2207

提示

样例 2 解释

1.选择 $2×2=4$，黑板上的数字变为4 2 2。

2.选择 $2×2=4$，黑板上的数字变为4 4。

3.选择 $4+4=8$，黑板上的数字变为8。

经过其他选择验证，$8$ 为最小值。

数据范围

对于 $10\%$ 的数据，仅含有一种运算符号。
对于 $50\%$ 的数据，$0<N≤4$。
对于 $100\%$ 的数据，$0<N≤7$，且运算过程中的最大值不超过long long数据类型。