题目描述

IOI 98

多边形魔法阵启动规则是这样的:开始时有一个$\red{N}$个顶点的多边 形。如图所示,这里$\red{N=4}$。每个顶点有一个整数标记,每条边 上有一个"$\red{+}$"号或"$\red{*}$"号。边从$\red{1}$编号到$\red{N}$。

第一步,一条边被拿走;随后各步包括如下:

选择一条边$\red{E}$和连接着$\red{E}$的两个顶点$\red{V1}$和$\red{V2}$;

得到一个新的顶点,标记为$\red{V1}$与$\red{V2}$通过边$\red{E}$上的运算符运算的 结果。

最后,游戏中没有边,游戏的得分为仅剩余的一个顶点的值。 请看图的样例:

写一个程序,对于给定一个多边形,计算出可能的最高得分。

输入格式

输人共两行,第一行一个整数$\red{n}$表示顶点个数，第二行共$\red{2\times n}$个数，分别为数字和字 符。

例如:对于上图中的问题，我们可以这样按输人样例中的例子输人。数学中的"$\red{+}$"号代 表加法,小写字母"$\red{x}$"代表乘法。

输出格式

一个整数,计算最高得分。

样例

输入样例

5
10+-1x- 2x3+- 8x

输出样例

486