题目描述

Polygon 是一个在多边形上玩的游戏。游戏开始时，给定玩家一个具有 $n$ 个顶点和 $n$ 条边（编号为 $1 \sim n$）的多边形，如下图所示，$n=4$。

多边形的每个顶点有一个整数，每条边有一个运算符 +（加）或运算符 *（乘）。

玩法：

• 第一步，玩家选择一条边，将其删除。
• 随后的 $n-1$ 步：选择一条边连接的两个顶点 V1 和 V2，用边上的运算符计算 V1 和 V2，得到的结果作为一个新顶点替换这两个原来的顶点。
• 游戏结束时，只剩一个顶点，没有多余的边。

下面给出在上图进行游戏的全过程。玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分。上图玩家得分是0。

（翻译者友情提示：这里每条边的运算符旁边的数字为边的编号，不拿来计算）

编写一个程序，给定一个多边形，计算最高可能的分数。

输入格式

输入包含两行，描述一个有 n 个顶点的多边形。

第一行是正整数 n。

第二行共 2n 个读入，描述这个多边形所有边上的符号、顶点上的整数；每两个读入中第一个是字符，第二个是数字。第一个字符为第一条边的计算符号（ t 代表相加，x 代表相乘)，第二个读入代表顶点上的数字。从编号为 1 的边开始，边、点、边、点……按顺序描述。

• $3 \le n \le 50$

• 对于任何一系列的操作，保证顶点数字都在 $[-32768,32767]$ 的范围内。

输出格式

第一行，输出最高的分数。

第二行，将满足得到最高分数的情况下，所有的可以在第一步删除的边的编号从小到大输出，数据之间用一个空格隔开。

输入输出样例1

4
t -7 t 4 x 2 x 5

33
1 2