306017 - 多边形魔法阵

【题目描述】6.17 多边形魔法阵（MagicArray） IOI 98 多边形魔法阵启动规则是这样的：开始时有一个N个顶点的多边形。如图6.27所示，这里N＝4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。

   2
   +

(-7)-------(4) ! ! 1+ ! ! * 3

!         !
!         !

(5)-------(2)

    *
	4
第一步，一条边被拿走；随后各步包括如下：

选择一条边E和连接着E的两个顶点V1和 V2； 得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。 最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。 请看图6.28的样例：

   2
   +                 2   (4)             (4)

(-7)-------(4) + / 2 /

|                     /               + / 

1+ | (-2) (-4)/ (0)

|                    \
|                   *  \

(5)-------(2) 4 (2)

    *
	4
	

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

输入共两行，第一行一个整数n表示顶点个数，第二行共2×n个数，分别为数字和字符。例如：对于上图中的问题，我们可以这样按输入样例中的例子输入，数学中的“+”号代表加法，小写字母“x”代表乘法。

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