# 题目可能有些许修改，但大意一致

多边形是一个玩家在一个有 $n$ 个顶点的多边形上的游戏，如图所示，其中 $n＝4$。每个顶点用整数标记，每个边用符号 `+`（加）或符号 `*`（乘积）标记。

![img](https://cdn.luogu.org/upload/pic/16086.png)

第一步，删除其中一条边。随后每一步：

选择一条边连接的两个顶点 $V1$ 和 $V2$，用边上的运算符计算 $V1$ 和 $V2$ 得到的结果来替换这两个顶点。

游戏结束时，只有一个顶点，没有多余的边。

如图所示，玩家先移除编号为 $3$ 的边。之后，玩家选择计算编号为 $1$ 的边，然后计算编号为 $4$ 的边，最后，计算编号为 $2$ 的边。结果是 $0$。

![img](https://cdn.luogu.org/upload/pic/16088.png)

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

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

## 输入格式

输入描述一个有 $n$ 个顶点的多边形，它包含两行。第一行是数字 $n$，为总边数。

第二行描述这个多边形，一共有 $2n$ 个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号(`t`代表相加，`x`代表相乘)，第二个代表顶点上的数字。首尾相连。

$3\le n \le 50$

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

## 输出格式

第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。

感谢 @2016c01 提供的翻译

题目可能有些许修改，但大意一致

多边形是一个玩家在一个有 $n$ 个顶点的多边形上的游戏，如图所示，其中 $n＝4$。每个顶点用整数标记，每个边用符号 +（加）或符号 *（乘积）标记。

第一步，删除其中一条边。随后每一步：

选择一条边连接的两个顶点 $V1$ 和 $V2$，用边上的运算符计算 $V1$ 和 $V2$ 得到的结果来替换这两个顶点。

游戏结束时，只有一个顶点，没有多余的边。

如图所示，玩家先移除编号为 $3$ 的边。之后，玩家选择计算编号为 $1$ 的边，然后计算编号为 $4$ 的边，最后，计算编号为 $2$ 的边。结果是 $0$。

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

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

输入格式

输入描述一个有 $n$ 个顶点的多边形，它包含两行。第一行是数字 $n$，为总边数。

第二行描述这个多边形，一共有 $2n$ 个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号(t代表相加，x代表相乘)，第二个代表顶点上的数字。首尾相连。

$3\le n \le 50$

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

输出格式

第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。

感谢 @2016c01 提供的翻译