3209 - 多边形（Polygon）
多边形是一个玩家在一个有n个顶点的多边形上的游戏，如图所示，其中n＝4。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。
然后需要先删除一条边：
然后可以任意选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。比如：
最终只会剩下一个数字（节点）。
你需要求出所有方案能够使得最终的数字尽可能的大。还有求出（第一步的）删除那些边可能使得最终的数字是那个最大值。
输入
输入描述一个有n个顶点的多边形，它包含两行。第一行是数字n，为总边数。
第二行描述这个多边形，一共有2n个读入，每两个读入中第一个是字符，第二个是数字。
第一个字符为第一条边的计算符号(t代表相加，x代表相乘)，第二个代表顶点上的数字。首尾相连。
3 < = n < = 50
对于任何一系列的操作，顶点数字都在[- 10^6,10^6]的范围内。
输出
第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。
样例
输入
4 t -7 t 4 x 2 x 5
输出
33 1 2
输入
10 t -6 t 6 x 2 t -5 t -6 x -1 t 4 t -2 t 7 x 1
输出
3048 2
提示
只要先删除边1或者边2，然后让4、2、5先做乘法，最后和-7相加，都能达到最大值33。其余删除的边都不能使得最大值为33。
来源
IOI