题目描述

多边形游戏是一种在一个具有 n 个顶点的多边形上进行的游戏。每个顶点有个权值（整数）。如图 1 是一个 n = 4 对应多边形，每个顶点上都有一个整数，每条边都有一个运算符 + 或者 * ，所有边按从 1 到 n 进行编号。
游戏都首先移除一条边，接下来可以进行如下操作：

选择一条边E 和与之相关联的点 V1 和 V2，用一个新的点替换它们，新点上的整数为 V1, V2 上的整数用 E 上的操作符运算后的结果。
没有边时游戏结束，游戏得分就是最后剩下的那个顶点上的整数。
对于图 1 中的多边形，如果游戏者首先去掉3，然后依次去掉 1、4、2，最后得分将是 0。

请你写一个程序，对于给定的多边形，计算出可能得到的最高分，并列出第一步移除哪些边可以得到这个最高分。

输入格式

共两行，第一行是一个正整数 n，表示多边形的边数。
接下来一行是这个多边形的描述，包含 n 条边和 n 个顶点，加号边用 t 表示，乘号边用 x 表示，顶点用顶点上标的整数表示，输入按照边的编号从 1 到 n 的顺序给出。

输出格式

共两行，第一行输出可能得到的最高分。
第二行输出一些边的列表，只有第一步移除的边在这个列表中才可能得到最高分。每条边都用这个边上的编号表示，列表必须是升序的。

样例输入

4
t -7 t 4 x 2 x 5

样例输出

33
1 2

数据范围

对于100%的数据，3 <= n <= 30, -5 <= E <= 17

限制

1s

来源

POJ1179
CWOI新高二专题测试三